Dynamic Programming versus Greedy for a Coin Change Till
A shop till must give change for any amount from 1 to 99 cents using the fewest coins. The available denominations are 1, 5, 10, and 25 cents. The shop first used a greedy algorithm: take the largest coin that fits, repeat. This works for most amounts, but the manager wants a proof it is always optimal, and is worried about a future change to the coin set (for example, adding a 20-cent coin or switching to 1, 4, 6, and 10 cents). A cashier reports that with denominations 1, 4, 6, 10, greedy gives 6 coins for 18 cents (10 + 4 + 4) while a colleague claims 3 coins (6 + 6 + 6) is possible.
1. Verify the cashier's claim for 18 cents with denominations 1, 4, 6, 10, and explain why greedy fails here.
Read the worked answer
Greedy on 18 with {1, 4, 6, 10}: take 10 (remainder 8), take 6? No, 6 > 8? 6 ≤ 8, so take 6 (remainder 2), then two 1s. That gives 10 + 6 + 1 + 1 = 4 coins, not 6. Let me recheck the cashier's figure: 10 + 4 + 4 = 18 uses 3 coins, and 6 + 6 + 6 = 18 uses 3 coins. So the cashier's '6 coins' is wrong; both greedy and the alternative use 3 coins here.
A cleaner counterexample for greedy with {1, 4, 6, 10}: amount 12. Greedy takes 10 + 1 + 1 = 3 coins; optimal is 6 + 6 = 2 coins. So greedy fails at 12, using 3 coins where 2 suffice. Another: amount 8 - greedy takes 6 + 1 + 1 = 3; optimal is 4 + 4 = 2. The failure mechanism: greedy commits to the largest coin without considering that a slightly smaller coin may combine better. The greedy choice is locally optimal but not globally optimal because the coin set lacks the canonical property.
2. Explain why greedy is optimal for {1, 5, 10, 25} but not for {1, 4, 6, 10}, and how you would prove optimality.
Read the worked answer
For {1, 5, 10, 25}, the coin system is canonical: greedy is optimal for every amount. A proof uses an exchange argument. Consider any optimal solution. For the 25-cent coin: any solution using five or more 5-cent coins, or twenty-five 1-cent coins, can be improved by replacing them with a 25-cent coin, so an optimal solution uses as many 25s as possible subject to the remainder. Similarly, two 5s can be replaced by a 10, and two 10s by a 20 - but 20 is not a coin, so the argument must handle the 10-and-5 combinations carefully. The standard proof shows that for each denomination, the greedy count is at least as large as in any optimal solution, by bounding the number of smaller coins that could substitute (e.g. at most one 10 and one 5 below 25, because two 10s = 20 < 25 but a 25 would be better if possible).
For {1, 4, 6, 10}, the system is not canonical. The counterexample 12 = 6 + 6 (2 coins) versus greedy's 10 + 1 + 1 (3 coins) disproves optimality. The exchange argument fails because 6 + 6 = 12 cannot be improved by a 10, and no coin equals 12, so the 'replace smaller coins with a larger one' step does not hold. Proving optimality requires either a full exchange argument (which fails here) or a dynamic-programming verification that greedy matches the optimum for all amounts up to some bound.
3. Design a dynamic programming solution that is correct for any coin set and compare its complexity to greedy.
Read the worked answer
Define dp[a] = minimum coins to make amount a, with dp[0] = 0. Recurrence: dp[a] = 1 + min over coins c ≤ a of dp[a − c]. Compute a from 1 to 99 (or up to the maximum amount). To reconstruct the coins, store a choice array. Correctness follows from optimal substructure: any optimal solution for a uses some coin c first, and the remainder a − c must itself be optimally solved, otherwise a better solution for a would exist. This holds for any coin set, including {1, 4, 6, 10} and sets with no 1-cent coin (where some amounts are unreachable; set dp[a] = ∞).
Complexity: O(A × k) time and O(A) space, where A is the maximum amount and k the number of denominations. For A = 99 and k = 4, that is 396 operations - trivial. Greedy is O(A / min coin) or O(k log k + A) depending on implementation, faster but not always correct.
The trade-off: greedy is faster and simpler but correct only for canonical coin systems; DP is slightly slower but correct for all systems. For a till handling amounts up to 99 cents, DP is cheap enough that correctness should win. The judgement is recognising that the coin set determines whether the fast algorithm is valid, and that a small, bounded problem justifies the robust algorithm.