Example - Coin Change (Greedy Works)

Make change for $67$ cents using US coins ($25$, $10$, $5$, $1$). Minimize the number of coins. Greedy approach: always pick the largest coin that fits. $1.$ $67$ cents: take $25$ ($42$ left)

$2.$ $42$ cents: take $25$ ($17$ left)

$3.$ $17$ cents: take $10$ ($7$ left)

$4.$ $7$ cents: take $5$ ($2$ left)

$5.$ $2$ cents: take $1$, take $1$ ($0$ left) Total: $6$ coins. That's optimal for US coins. Why does greedy work here? Because US coins form a canonical system: each coin divides evenly into larger ones. This structure guarantees greedy works.