A greedy algorithm builds a solution step by step: at each step it takes the best-looking option and never changes it. There is no search or going back, so the running time is usually O(n log n) (sorting) or O(n). The price: it is correct only for some problems.

When greedy works

  • Greedy-choice property: the best local choice can be part of an optimal solution.
  • Optimal substructure: after the choice, an optimum of the remaining problem extends to an optimum of the whole.

Making change

Greedy makes 6 as 4+1+1, the optimum is 3+3
Greedy makes 6 as 4+1+1, the optimum is 3+3
python
from itertools import combinations_with_replacement

def greedy_coins(coins, amount):
    result = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

def optimal_coins(coins, amount):
    for k in range(1, amount + 1):
        for combo in combinations_with_replacement(coins, k):
            if sum(combo) == amount:
                return list(combo)

print(greedy_coins([1, 5, 10, 25], 63))
print(greedy_coins([1, 3, 4], 6), optimal_coins([1, 3, 4], 6))

With coins 1, 5, 10, 25 greedy is always optimal. With coins 1, 3, 4 and amount 6 it takes 4 + 1 + 1 (3 coins) while the optimum is 3 + 3 (2 coins). The answer is valid but not optimal.