动态规划背包

Question

我正在尝试解决这个问题，但是有几个测试用例失败了。我正在使用备忘录 table 调用 arr 来优化递归。

我可能做错了什么？

s=list(map(int,input().split()))
n=s[0]
W=s[1]
value=[-1]
weight=[-1]
for i in range(n):
    t=list(map(int,input().split()))
    weight.append(t[0])
    value.append(t[1])


arr=[[-1]*(W+1)]*(n+1)

def KS(n,W):
    if n==0 or W==0:
        return 0
    if arr[n][W]!=-1:
        return arr[n][W]
    if weight[n]>W:
        answer=KS(n-1,W)
    else:
        answer=max(value[n]+KS(n-1,W-weight[n]),KS(n-1,W))
    arr[n][W]=answer
    return answer

result=KS(n,W)
print(result)

Answer 1

当您在列表 [[-1]*(W+1)] 上执行 *(n+1) 时，您实际上是在创建具有相同引用的多个列表。

您可以尝试使用 arr = [[-1]*(W+1) for i in range(0,(n+1))] 而不是 arr=[[-1]*(W+1)]*(n+1)。

因此，当您更改一个列表时，更改也会反映在其他列表中，因为它们都指向同一个列表。

W, n = 3, 3
arr = [[-1]*(W+1)]*(n+1)
print(arr)
arr[0][0] = -2
print(arr)

输出

[[-1, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1]]
[[-2, -1, -1, -1], [-2, -1, -1, -1], [-2, -1, -1, -1], [-2, -1, -1, -1]]

请注意我如何更改 arr[0][0]，但 arr[1][0]、arr[2][0] 和 arr[3][0] 也会更改。

但是有了这个

W, n = 3, 3
arr = [[-1]*(W+1) for i in range(0,(n+1))]
print(arr)
arr[0][0] = -2
print(arr)

输出

[[-1, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1]]
[[-2, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1]]

只有 arr[0][0] 改变了。

如果这有效，那么您可以查看 List of lists changes reflected across sublists unexpectedly 以获取有关此的更多信息。

注意：我没有运行你的全部代码，所以我不能保证你的算法实现的正确性。

动态规划背包

Dynamic Programming Knapsack

python

recursion

knapsack-problem

dynamic-programming