01 knapsack problem code example

Example 1: greedy knapsack

def greedy_knapsack(values,weights,capacity):
    n = len(values)
    def score(i) : return values[i]/weights[i]
    items = sorted(range(n)  , key=score , reverse = True)
    sel, value,weight = [],0,0
    for i in items:
        if weight +weights[i] <= capacity:
            sel += [i]
            weight += weights[i]
            value += values [i]
    return sel, value, weight


weights = [4,9,10,20,2,1]
values = [400,1800,3500,4000,1000,200]
capacity = 20

print(greedy_knapsack(values,weights,capacity))

Example 2: python 0-1 kanpsack

#Returns the maximum value that can be stored by the bag

def knapSack(W, wt, val, n):
   # initial conditions
   if n == 0 or W == 0 :
      return 0
   # If weight is higher than capacity then it is not included
   if (wt[n-1] > W):
      return knapSack(W, wt, val, n-1)
   # return either nth item being included or not
   else:
      return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
         knapSack(W, wt, val, n-1))
# To test above function
val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
n = len(val)
print (knapSack(W, wt, val, n))