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