Practice question · Multiple choice
Greedy change-making with British coins always gives the fewest coins, and with the coin set {1, 15, 20} it fails on 40 - taking 20+15+1+1+1+1+1 instead of 20+20. Why does the same algorithm succeed on one coin set and fail on another?
Hints
- Take the largest coin first on 40 with {1, 15, 20}. What did that first choice cost you?
- Ask what would have to be true of a coin system for the greedy choice to be safe.
Show the answer
C. Because greedy is optimal only when the problem has the right structure.
Why
The failure is clearest on 30: greedy takes 20 and needs ten 1s, where 15+15 uses two coins, a locally best first choice has cut off the better solution. Whether that can happen is a property of the system, to be proved rather than assumed. Greedy is provably optimal for Huffman coding and minimum spanning trees, each with an exchange argument behind it.
Practise Greedy Choices and Counterexamples
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Greedy Choices and Counterexamples
- Select every true statement about greedy algorithms.
- Dijkstra's shortest-path algorithm is greedy and provably optimal, until an edge has negative weight, when it…
- Order what happens when greedy makes change for 30 with coins {1, 15, 20}.
- Sort each problem by whether the greedy approach is provably optimal or can fail.