Greedy algorithms 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: greedy algorithm

greedy algorithm:
	makes the optimal choice at each step