What Makes Greedy Work

The Idea

A greedy algorithm takes the move that looks best right now and never revisits it. No search tree, no undo — one pass.

That is only correct when a local win can never cost you a better global answer. The usual proof is an exchange argument: take any optimal answer, swap the greedy choice into it, and show the result is still optimal. If that swap always survives, greedy is safe. One counterexample and it is not.

Real-World Example

Handing back change at a till. With coins of 25, 10, 5 and 1, grabbing the largest coin that still fits is always optimal. Mint a currency of 1, 3 and 4 and the same reflex pays 4 + 1 + 1 for six, where two threes would have done.

The Code

def greedy_coins(coins, amount):
    used = 0
    for c in sorted(coins, reverse=True):   # biggest coin first
        used += amount // c                 # take as many as still fit
        amount %= c
    return used

print(greedy_coins([25, 10, 5, 1], 30))     # -> 2, and 2 is optimal
print(greedy_coins([1, 3, 4], 6))           # -> 3, but 3 + 3 is only 2

print(greedy_coins([1, 5, 7], 10))