用动态规划求子集和

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]

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

Answer 1

如果只提供正值，我不太明白为什么需要二维列表。您可以简单地使用1d列表：

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

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

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

之后，列表可能显示从0到（并包括sum）的每个值是否可以构造它。因此，如果可能的[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，用<代码>5，用<代码>2,3，等等来构造。