python - 01 python中的背包动态规划

Question

def printtable(arr):
    for row in arr:
        print(row)
    return

items = [(3,2),(4,3),(5,4),(6,5)]
W = 5

arr = [[0]*(W+1)]*(len(items)+1)

for i in range(1,len(items)+1,1):
    val,wt = items[i-1]
    for w in range(1,W+1,1):
        if wt <= w:
            arr[i][w] = max(arr[i-1][w] , val + arr[i-1][w-wt])
        else:
            arr[i][w] = arr[i-1][w]

printtable(arr)

输出为:

[0, 0, 3, 4, 6, 7]
[0, 0, 3, 4, 6, 7]
[0, 0, 3, 4, 6, 7]
[0, 0, 3, 4, 6, 7]
[0, 0, 3, 4, 6, 7]

我不知道这段代码有什么问题？值(value)观是错误的。但代码中的逻辑是正确的。

预期输出是:

0 0 0 0 0 0
0 0 3 3 3 3
0 0 3 4 4 7
0 0 3 4 5 7
0 0 3 4 5 7

Answer 1

问题在于如何创建列表列表。当你这样做时 -

arr = [[0]*(W+1)]*(len(items)+1)

这将创建一个内部列表，外部列表中的每个列表都是对同一列表的引用。显示此问题的示例 -

>>> a = [[0]*5]*5
>>> print(a)
[[0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0]]
>>> a[0][0] = 1
>>> print(a)
[[1, 0, 0, 0, 0],
 [1, 0, 0, 0, 0],
 [1, 0, 0, 0, 0],
 [1, 0, 0, 0, 0],
 [1, 0, 0, 0, 0]]

<小时/>

您应该使用列表理解 -

arr = [[0 for _ in range(W+1)] for _ in range(len(items)+1)]