python,满分，砝码称重【第十二届】【省赛】【研究生组】

完整源代码在文章末尾，首先这种涉及到二维数组的优化问题，优先考虑动态规划

 核心思路：

先构建一个二维python列表（详情参考(341条消息) python 二维列表（数组）赋值问题_z小白的博客-CSDN博客_python创建二维数组赋值）

（通过代码）

然后再变成这样

为什么这里要多一行，多一列呢？

为了方便以下三个条件

        1.dp[i][j] = dp[i-1][j] or \#已经可以表示，这个i砝码不用放
        2.dp[i-1][abs(j-w[i-1])] or \#是重了吗？这个i砝码放在另一边，减重
        3.dp[i-1][j+w[i-1]]#是轻了吗？这个i砝码放在同一边，增重

一、特别是第2个条件dp[i-1][abs(j-w[i-1])] 中的abs(j-w[i-1])，

如题目测试样例：

3

1 4 6

其中输入考虑1时，有dp[1][1] = dp[1 - 1][abs(1 - w[0])] = dp[1 - 1][abs(1 - 1)]= dp[0][0] = 1

其中输入考虑4时，有dp[2][4] = dp[2 - 1][abs(4 - w[1])] = dp[2 - 1][abs(4 - 4)]= dp[1][0] = 1

等，所以把第0列全部变为1，为了使这种情况成立，

这个点的思路来源：当然实际不是一下得出来的，是调试出1和4都为0时候不对，才知道dp[0][0]=dp[1][0]是本该成立的要设置为1，

二、对第三个条件dp[i-1][j+w[i-1]]，当然为了避免地址越界，需要以下代码区分以下，即如果存在越界则该条件失效，否则考虑该条件，如下截图：

 这是主要的地方，其它的地方与动态规划类似，文章末尾有参考博客可以看一下。

N = int(input())
str1 = input()
#权重矩阵
w = []
w = [int(x) for x in str1.split(" ")]
sum = 0
for x in w:
    sum += x
    
#初始化result二维列表为0,
dp = [[0]*(sum+1) for x in range(len(w)+1)]
#更新result列表
dp[0][0] = 1#初始
for i in range(1,len(w)+1):
    dp[i][0] = 1#****************************
    for j in range(1,sum+1):
        
        #if主要针对dp[i-1][j+w[i-1]]这个条件，避免越界
        '''
            dp[i][j] = dp[i-1][j] or \#已经可以表示，这个i砝码不用放
        dp[i-1][j-w[i-1]] or \#是重了吗？这个i砝码放在另一边，减重
        dp[i-1][j+w[i-1]]#是轻了吗？这个i砝码放在同一边，增重
        '''
        if j + w[i-1] <= sum:
            dp[i][j] = dp[i-1][j] or \
            dp[i-1][abs(j-w[i-1])] or dp[i-1][j+w[i-1]]
        else:
            dp[i][j] = dp[i-1][j] or \
            dp[i-1][abs(j-w[i-1])]
    #print(dp)
 
#更新完毕统计最后一行（除去第0列）1的个数，（由*号行知道，第0列全为1，只是为了规划这条语句dp[i-1][abs(j-w[i-1])使用，不作为参考）
count = 0
for i in range(1,sum+1):
    if dp[len(w)][i] == 1:
        count += 1
print(count)

参考的一位，c语言实现的：试题 历届真题 砝码称重【第十二届】【省赛】【B组】_LightningJie的博客-CSDN博客