使用动态规划查找子集和

Question

使用动态规划查找子集和

3

我正在练习动态规划，但是在调试代码时遇到了困难。我的想法是在给定一组数字的情况下找出是否存在可能的和。以下是我的代码：

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。不完全确定我做错了什么，任何有助于理解这一点的帮助都将不胜感激。

- Stupid.Fat.Cat

我不太明白为什么你需要一个二维列表... - Willem Van Onsem

你知道你在这里做什么吗？如果你只是想知道是否可以使用硬币总和达到给定的值，你可以使用1d列表。 - Willem Van Onsem

你能重复使用一个硬币，还是每个数字只能使用一次？ - Willem Van Onsem

你只能使用该元素一次。 - Stupid.Fat.Cat

负面硬币可能吗？如果不行，这可以通过一个一维数组轻松实现。 - Willem Van Onsem

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Willem Van Onsem · Accepted Answer

考虑到您只输入正值，我不太明白为什么需要一个二维列表。您可以使用一个一维列表:

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。

对于给定的coins和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]可以构建出3；使用价值为2和3的硬币[2,3]可以构建出5，等等。