# 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))