Making Change: The Greedy Algorithm

Problem statement

Given a till with unlimited supplies of coins in certain denominations (listed in descending order), find a combination of coins that sums to a target amount. The goal is to minimise the number of coins.

Greedy approach

The algorithm always tries the largest coin first: if the largest coin does not exceed the remaining amount, use it and recurse on the reduced amount. Otherwise, discard that coin denomination and try the next largest.

let rec change till amt =
  match till, amt with
  | _, 0         -> []
  | [], _        -> raise (Failure "no more coins!")
  | c::till, amt -> if amt < c then change till amt
                    else c :: change (c::till) (amt - c)

Key design decisions

• Base case of zero, not one: when amt = 0, the result is [] (no coins needed). Using zero as the base case is simpler than using one; most iterative procedures are cleanest when they do nothing in the base case. A base case of one is often a sign of a novice programmer.
• The coin is not removed from the till after use: the recursive call uses c::till (not till), since we have unlimited supply of each coin.
• Failure via exceptions: if the till becomes empty while the amount is still nonzero, the function raises Failure.

Greedy failure

The greedy algorithm is not always correct. Example: making 6 using coins [5, 2].

Step	Till	Amount	Action
1	[5; 2]	6	Take 5 (largest ≤ 6)
2	[5; 2]	1	5 > 1, skip 5
3	[2]	1	2 > 1, skip 2
4	[]	1	Failure!

Yet 6 = 2 + 2 + 2 is a valid solution. The greedy algorithm fails because it commits to the 5 coin and cannot backtrack. Greedy algorithms work for certain coin systems (e.g., UK coins: 1, 2, 5, 10, 20, 50) but not in general.