49. Example of Greedy: Coin Change Problem (Simple Case)

The Coin Change problem asks: given a set of coin denominations, what is the minimum number of coins required to make a given amount?

US Coin System (Where Greedy Works)

In standard US currency (1, 5, 10, 25 cents), the greedy approach (always choosing the largest denomination possible) guarantees the minimum number of coins.

Goal: 41 cents

1. Take the largest coin <= 41: 25. Remaining: 16.
2. Take the largest coin <= 16: 10. Remaining: 6.
3. Take the largest coin <= 6: 5. Remaining: 1.
4. Take the largest coin <= 1: 1. Remaining: 0.

Total coins: 4. This is the optimal solution.

The Algorithm

python coins = [25, 10, 5, 1] # Assumes sorted descending def greedy_change(amount, coins): count = 0 for coin in coins: while amount >= coin: amount -= coin count += 1 return count