1#Returns the maximum value that can be stored by the bag
2
3def knapSack(W, wt, val, n):
4 # initial conditions
5 if n == 0 or W == 0 :
6 return 0
7 # If weight is higher than capacity then it is not included
8 if (wt[n-1] > W):
9 return knapSack(W, wt, val, n-1)
10 # return either nth item being included or not
11 else:
12 return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
13 knapSack(W, wt, val, n-1))
14# To test above function
15val = [50,100,150,200]
16wt = [8,16,32,40]
17W = 64
18n = len(val)
19print (knapSack(W, wt, val, n))
1# a dynamic approach
2# Returns the maximum value that can be stored by the bag
3def knapSack(W, wt, val, n):
4 K = [[0 for x in range(W + 1)] for x in range(n + 1)]
5 #Table in bottom up manner
6 for i in range(n + 1):
7 for w in range(W + 1):
8 if i == 0 or w == 0:
9 K[i][w] = 0
10 elif wt[i-1] <= w:
11 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
12 else:
13 K[i][w] = K[i-1][w]
14 return K[n][W]
15#Main
16val = [50,100,150,200]
17wt = [8,16,32,40]
18W = 64
19n = len(val)
20print(knapSack(W, wt, val, n))