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?
