Solve Knapsack Problem
Knapsack Problem using Memory Function:
- Description of the Problem:
Given weights and values of n items, put these items in a knapsack of capacity W to get themaximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] andwt[0..n-1] which represent values and weights associated with n items respectively. Also givenan integer W which represents knapsack capacity, find out the maximum value subset of valsuch that sum of the weights of this subset is smaller than or equal to W. You cannot break anitem, either pick the complete item, or don’t pick it (0-1 property).
• wt[1…n] to be the weight array.
• val[1…n] to be the value array.
• W to be the capacity of knapsack.
• table[0…n][0…W] to be the table for using top-down approach and it to be intialized
as mentioned in assignment.
Pseudo code of the function which takes i(no. Of weights) and j(capacity) as inputs:
1. if table[n][W] != -1
3. return table[n][W]
5. ifwt[n-1] > W
11. return max of (val[n-1] + knapSack(W-wt[n-1],n-1)) and (knapSack(W,n-1))
• The Data Structure used for the Table is 2-D array(list).
• Hash-Table (Hash-Map in fact) can also be used here ( by inserting all the computed
KnapSack(i,j)’s into the Hash-Map). But here a 2-D array is used because it is simple
• Time Complexity is same as Bottom-Up approach.
• It is easy to observe that the Time Complexity is O(nW).
• Space Complexity is same as Bottom-Up approach, but the Recursion Stack could be
as deep as max(n,W).
• Because of the above said problem, Bottom-Up approach is preffered over Top-Down
approach for high values of n and W.
• Came to know about the Top-Down approaches.
• Found Implementing the Top-Down approach Easier when compared with Bottom-Up
• Found Bottom-Up approach to be more spatially effiecent the Top-Down couterpart.
6) Run the Program:
• Extract the .zip file and open the folder in the terminal.
• Run the assignment.py file by writing the command
• Program asks for n, weights, values and the Knapsack capacity. Provide them.
• Program prints the maximum value.
# If table content is not empty return the table content
# Else calculate knapSack(W,n)
if table[n][W] != -1:
if n == 0 or W == 0 :
# If weight of the nth item is more than Knapsack of capacity
# W, then this item cannot be included in the optimal solution
if (wt[n-1] > W):
# return the maximum of two cases:
# (1) nth item included
# (2) not included
return max(val[n-1] + knapSack(W-wt[n-1],n-1),
# To test above function
print(‘Enter n : ‘,end=”)
n = int(input())
val = 
wt = 
# scanning of weights values and W
for i in range(n):
print(‘Enter val[‘+str(i)+’] : ‘,end=””)
print(‘Enter wt[‘+str(i)+’] : ‘,end=””)
print(‘Enter W : ‘,end=””)
W = int(input())
#creating a table to use top down approach
table = 
temporary_list = 
for j in range(W+1):
for i in range(n+1):
for j in range(W):