Greedy coin change
A greedy algorithm makes the choice that looks best right now and never revisits it. For change, that means always taking the biggest coin that still fits. It is fast and simple, and for everyday coins it happens to be right. For some coin sets it is not.
2010521
coins taken (amount left: 38)
Make 38 from these coins using as few as possible. The greedy idea: always take the biggest coin that still fits.
1function greedyChange(coins, amount) {2 const used = [];3 for (const c of [...coins].sort((a, b) => b - a)) {4 while (amount >= c) {5 amount -= c;6 used.push(c);7 }8 }9 return amount === 0 ? used : null;10}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | k log k | sorting k coin types; then one step per coin taken |
| average | k log k + c | c is the number of coins taken |
| worst | k log k + c | but the answer itself can be wrong |
| space | c | the list of coins taken |
Where it breaks
- Greedy can lose. Pick Greedy loses: with coins 1, 3 and 4, greedy makes 6 as 4 + 1 + 1, three coins. Two 3s would do. Taking the 4 looked best and ruled out the better answer.
- Greedy can get stuck. Pick Greedy stuck: with 3s and 5s, greedy takes a 5, then a 3, and is left with 1 it cannot make. Yet three 3s make 9. Greedy never goes back to try something else.
- When greedy is safe. For coin systems like euros or dollars, greedy is always optimal, which is why cashiers do it. For any coin set, dynamic programming gives the true minimum.