greedy knapsack

1def greedy_knapsack(values,weights,capacity):
2    n = len(values)
3    def score(i) : return values[i]/weights[i]
4    items = sorted(range(n)  , key=score , reverse = True)
5    sel, value,weight = [],0,0
6    for i in items:
7        if weight +weights[i] <= capacity:
8            sel += [i]
9            weight += weights[i]
10            value += values [i]
11    return sel, value, weight
12
13
14weights = [4,9,10,20,2,1]
15values = [400,1800,3500,4000,1000,200]
16capacity = 20
17
18print(greedy_knapsack(values,weights,capacity))

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