Solve Knapsack Problem
Knapsack Problem using Memory Function:
Solution
- 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 val[]such 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).
- Design:
Assume:
• 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:
KnapSack(i,j):
1. if table[n][W] != -1
2. begin
3. return table[n][W]
4. end
5. ifwt[n-1] > W
6. begin
7. returnknapSack(W,n-1)
8. end
9. else
10. begin
11. return max of (val[n-1] + knapSack(W-wt[n-1],n-1)) and (knapSack(W,n-1))
12. end
Data Structures:
• 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
to use.
3) Complexities:
Time Complexity:
• Time Complexity is same as Bottom-Up approach.
• It is easy to observe that the Time Complexity is O(nW).
Space Complexity:
• 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.
5) Reflection:
Knowledge Gained:
• Came to know about the Top-Down approaches.
• Found Implementing the Top-Down approach Easier when compared with Bottom-Up
approach.
• 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
python3 assignment.py
• Program asks for n, weights, values and the Knapsack capacity. Provide them.
• Program prints the maximum value.
defknapSack(W,n):
# If table content is not empty return the table content
# Else calculate knapSack(W,n)
if table[n][W] != -1:
return table[n][W]
if n == 0 or W == 0 :
return 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):
returnknapSack(W,n-1)
# return the maximum of two cases:
# (1) nth item included
# (2) not included
else:
return max(val[n-1] + knapSack(W-wt[n-1],n-1),
knapSack(W,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=””)
val.append(int(input()))
print(‘Enter wt[‘+str(i)+’] : ‘,end=””)
wt.append(int(input()))
print(‘Enter W : ‘,end=””)
W = int(input())
#creating a table to use top down approach
table = []
temporary_list = []
for j in range(W+1):
temporary_list.append(0)
table.append(temporary_list)
temporary_list=[]
for i in range(n+1):
temporary_list.append(0)
for j in range(W):
temporary_list.append(-1)
table.append(temporary_list)
temporary_list=[]
print(knapSack(W,n))