python - 使用动态规划求子集和

Question

我正在练习动态编程，并且正在努力调试我的代码。这个想法是找出给定数字列表是否可以求和。这是我的代码:

a = [2,3,7,8,10]
sum = 11
b = list(range(1, sum+1))
m = [[False for z in range(len(b))] for i in range(len(a))]

for i, x in enumerate(b):
    for j, y in enumerate(a):
        if x==y:
            m[j][i]=True
        elif y<x:
            m[j][i] = m[j-1][i]
        else:
            m[j][i] = m[j-1][i] or m[j-i][y-x]

for i, n in enumerate(m):
    print(a[i], n)

这是输出:

2 [False, True, False, False, False, False, False, False, False, False, False]
3 [False, True, True, False, False, False, False, False, False, False, False]
7 [False, True, True, False, True, True, True, False, False, False, False]
8 [False, True, True, False, True, True, True, True, False, False, False]
10 [False, True, True, False, True, True, True, True, True, True, False]

据我了解，在我的 else 语句中，该算法应该向上移动 1 行，然后查看 x 和 y 的差异并检查该插槽是否可行。因此，例如在最明显的情况下，最后一行中的最后一个元素。那将是 10(y)-11(x)，它应该一直回到它上面一行的索引 1，正如我们所知，它是 True。不完全确定我做错了什么，任何有助于理解这一点的帮助将不胜感激。

Answer 1

如果您只输入正值，我不太明白您为什么需要二维列表。您可以简单地使用一维列表:

coins = [2,3,7,8,10]
sum = 11

接下来我们初始化列表possible，它说明是否有可能获得某个值。我们将 possible[0] 设置为 True 因为这个总和可以在没有硬币的情况下完成。

possible = [False for _ in range(sum+1)]
possible[0] = True

现在您遍历每个硬币，遍历列表并在可能的情况下“升级”值:

for coin in coins:
    for i in range(sum-coin,-1,-1):
        if possible[i]:
            possible[i+coin] = True

之后，possible 列表显示从 0 到(包括 sum)的每个值，您是否可以构造它。因此，如果 possible[sum] 为 True，则可以构造 sum。

对于给定的硬币和总和，一个人得到:

>>> possible
[True, False, True, True, False, True, False, True, True, True, True, True]

因此值 0、2、3、5、7、 8, 9, 10, 11 可以用硬币构造。

编辑:追踪硬币

您还可以通过稍微修改代码来跟踪硬币:

possible = [None for _ in range(sum+1)]
possible[0] = []
for coin in coins:
    for i in range(sum-coin,-1,-1):
        if possible[i] is not None:
            possible[i+coin] = possible[i]+[coin]

现在可能看起来像:

>>> possible
[[], None, [2], [3], None, [2, 3], None, [7], [8], [2, 7], [10], [3, 8]]

所以0可以用硬币构造[](没有硬币)； 2可以用[2]构造(一个硬币值2)，3用[ 3]、5 和 [2,3] 等