Coin Change (Greedy)

Pick the largest denomination ≤ remaining amount. Greedy is optimal for canonical systems (like US coins) but can fail for arbitrary sets.

Algorithm Steps

Sort denominations descending.
Take as many as possible of the current coin.
Reduce remaining amount and continue.

Amount

Speed (ms)

Coin 25

Take: 0

Coin 10

Take: 0

Coin 5

Take: 0

Coin 1

Take: 0

Remaining amount: 63

Progress towards paying the target amount.

Note: For non-canonical sets (e.g., [1,3,4]), greedy may not produce optimal solutions. Try changing denominations to see counterexamples.

Pseudocode

1procedure COIN_CHANGE_GREEDY(denoms, A)
2  sort denoms in decreasing order
3  for each coin d in denoms do
4    take floor(A / d) coins of d
5    A ← A mod d
6  end for
7end procedure

Practice Problems

Use Cases

Making change in canonical coin systems (cashiers, vending machines).
Resource allocation where largest units are preferred.
Greedy baselines for comparison against DP exact solutions.

Back to Job Scheduling Next: Kruskal MST