1

I tried coding 0/1 Knapsack Dynamic programming bottom-up approach in Python.

Code that I tried:

def knapSack(W, wt, val, n):
    matrix = [[0]*(W+1)]*(n+1)
    print(matrix)

    for i in range(n+1):
        for j in range(W+1):
            if i == 0 or j == 0:
                matrix[i][j] = 0

            elif wt[i-1] <= j:
                matrix[i][j] = max(val[i-1]+matrix[i-1][j-wt[i-1]], matrix[i-1][j])
                
            else:
                matrix[i][j] = matrix[i-1][j]
                
            
    return matrix[n][W]


def knapSack2(W, wt, val, n):
    t = [[0 for i in range(W+1)] for j in range(n+1)]
    print(t)

    for i in range(n+1):
        for j in range(W+1):
            if i == 0 or j == 0:
                t[i][j] = 0

            elif wt[i - 1] <= j:
                t[i][j] = max(val[i-1] + t[i-1][j - wt[i-1]], t[i-1][j])
                
            else:
                t[i][j] = t[i-1][j]
                

    return t[n][W]


n = 3
W = 4

wt = [1, 2, 3]
val = [4, 5, 1]
print(knapSack(W, wt, val, n))
print(knapSack2(W, wt, val, n))

The output that I'm getting is:

[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
16
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
9

Question: Why is there a difference in the output even if the Code for both the functions is exactly the same except declaration?

Like is there a difference between the following declarations even if the print function value is the same?

matrix = [[0]*(W+1)]*(n+1)
matrix = [[0 for i in range(W+1)] for j in range(n+1)]
Ajay Bhagchandani
  • 135
  • 2
  • 20
  • 1
    Does this answer your question? [List changes unexpectedly after assignment. How do I clone or copy it to prevent this?](https://stackoverflow.com/questions/2612802/list-changes-unexpectedly-after-assignment-how-do-i-clone-or-copy-it-to-prevent) or [List of lists changes reflected across sublists unexpectedly](https://stackoverflow.com/q/240178/8881141) – Mr. T Jan 17 '21 at 13:08
  • Yes, the second link helped the most. Thanks @Mr.T – Ajay Bhagchandani Jan 17 '21 at 13:17
  • Link to actual (more appropriate) solution: https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly – Ajay Bhagchandani Jan 17 '21 at 13:21
  • 1
    The underlying principle is the same, though. But I understand that the second link is easier to link to your example, hence I added it. – Mr. T Jan 17 '21 at 13:23

0 Answers0