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))
1I don't know if the output is all correct. For me the output order in this case should be [4, 2, 0, 5] and not [4, 2, 5, 0], because the index 0 have more density than index 5. What dou you think?