Difference in Outputs of classical knapsack problem

Question

I wrote a program for a classical knapsack problem and it is working good.

Below is the code:

class Solution:

    def knapsack(self, wt, val, crr_cap, n):
        if crr_cap == 0 or n == 0:
            return 0

        b = self.knapsack(wt, val, crr_cap, n - 1)

        if wt[n - 1] <= crr_cap:
            a = val[n - 1] + self.knapsack(wt, val, crr_cap - wt[n - 1], n - 1)
            return max(a, b)

        else:
            return b

    def getMaximumvalue(self, weight, value, capacity) -> int:

        ret = self.knapsack(weight, value, capacity, len(weight))
        return ret


a = Solution()
weight = [1, 2, 3, 4, 5, 6]
value = [4, 5, 6, 7, 8, 9]

Then I added memoization to it, basically by adding 4 new lines.

Below is the updated code:

class Solution:
    def __init__(self):
        self.dp = None

    def knapsack(self, wt, val, crr_cap, n):
        if crr_cap == 0 or n == 0:
            return 0

        """
        Below is the new added condition
        Checking if the value is present in the cache
        """
        if self.dp[n][crr_cap] != -1:
            return self.dp[n][crr_cap]

        b = self.knapsack(wt, val, crr_cap, n - 1)

        if wt[n - 1] <= crr_cap:
            a = val[n - 1] + self.knapsack(wt, val, crr_cap - wt[n - 1], n - 1)
            """
            Added new line
            Adding the value to the cache
            """
            self.dp[n][crr_cap] = max(a, b)
            return max(a,b)
        
        else:
            """
            Added new line
            Adding the value to the cache
            """
            self.dp[n][crr_cap] = b
            return b
        
    def getMaximumvalue(self, weight, value, capacity) -> int:

        ret = self.knapsack(weight, value, capacity, len(weight))
        return ret


a = Solution()
"""
Constraints:
len(weight) <= 10 (n)
capacity <= 20 (crr_cap)

Note:
a.dp is a matrix with [capacity + 1][len(weight) + 1]
"""
weight = [1, 2, 3, 4, 5, 6]
value = [4, 5, 6, 7, 8, 9]
a.dp = [[-1] * (20 + 2)] * (len(weight) + 2)

Inputs of both the programs:

output = a.getMaximumvalue(weight, value, 0)
print(output)

output = a.getMaximumvalue(weight, value, 2)
print(output)

output = a.getMaximumvalue(weight, value, 4)
print(output)

output = a.getMaximumvalue(weight, value, 6)
print(output)

output = a.getMaximumvalue(weight, value, 8)
print(output)

output = a.getMaximumvalue(weight, value, 10)
print(output)

output = a.getMaximumvalue(weight, value, 12)
print(output)

output = a.getMaximumvalue(weight, value, 14)
print(output)

output = a.getMaximumvalue(weight, value, 16)
print(output)

output = a.getMaximumvalue(weight, value, 18)
print(output)

output = a.getMaximumvalue(weight, value, 20)
print(output)

Output of 1st program

0
5
10
15
17
22
24
26
31
33
35

Output of 2nd program

0
5
10
15
20
25
30
35
40
45
50

But the code is giving different outputs for certain inputs. What is the mistake in the 2nd program?

Answer 1

The issues is in the way a.dp is created.

a.dp = [[-1] * (20 + 2)] * (len(weight) + 2)

This causes problems as mentioned here: list-of-lists-changes-reflected-across-sublists-unexpectedly

To resolve this issue use the following code to declare and initialize the lists.

a.dp = []

for i in range(b):
    tmp = []
    for j in range(cap):
        tmp.append(-1)
    a.dp.append(tmp)