蓝桥杯2021年第十二届省赛真题-砝码称重

解题思路: 动态规划

注意事项: 创建一个dp矩阵,以题中的例子为例，个数是3，三个砝码的重量之和是11，所以创建3*12的矩阵，创建12列能够保证下标就是砝码的和

参考代码:

n = int(input())

list1 = list(map(int, input().strip().split()))

Sum = 0

for i in list1:

    Sum += i

matrix = [[False] * (Sum + 1) for x in range(n)]

for i in range(Sum):

    if(list1[0] == i):

        matrix[0][i] = True

for m in range(n -1):

    for k in range(Sum):

        if(matrix[m][k]):

            matrix[m + 1][k] = True

            matrix[m + 1][k + list1[m+1]] = True

            matrix[m + 1][abs(k - list1[m+1])] = True

            matrix[m + 1][list1[m + 1]] = True

result = 0

for i in range(1, Sum +1):

    if(matrix[n-1][i]):

        result += 1

print(result)