python 0 1 kanpsack

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