Dynamic Programming Knapsack

Question

I'm trying to solve this problem however several testcases fail. I'm using a memo table to called arr to optimize recursion.

What may I have done wrong?

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

When you perform *(n+1) on your list [[-1]*(W+1)], you are actually creating multiple lists with same reference.

You can try using arr = [[-1]*(W+1) for i in range(0,(n+1))] instead of arr=[[-1]*(W+1)]*(n+1).

So when you change one list the change is also reflected in other lists as they all point to the same list.

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

Output

[[-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]]

Notice how I change arr[0][0] but arr[1][0], arr[2][0] and arr[3][0] also change.

But with this

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

Output

[[-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]]

Only arr[0][0] is changed.

If this works then you can look into List of lists changes reflected across sublists unexpectedly for more information regarding this.

Note: I have not run your entire code, so I cannot vouch for the correctness of your implementation of the algorithm.