Practice question · Put in order
Order what happens when greedy makes change for 30 with coins {1, 15, 20}.
- Now 10 remains; take 1, since 15 and 20 are too big
- Take 20, the largest coin not exceeding 30
- Keep taking 1s until nothing remains
- End with 11 coins, worse than the optimal 2
Hints
- Greedy always grabs the largest coin that fits.
- After 20, no coin but 1 fits into the remaining 10.
Show the answer
- Take 20, the largest coin not exceeding 30
- Now 10 remains; take 1, since 15 and 20 are too big
- Keep taking 1s until nothing remains
- End with 11 coins, worse than the optimal 2
Why
Greedy grabs 20, then is forced onto ten 1s, ending at 11 coins, while two 15s would have done it in 2. A locally best first move led straight to a globally worse answer.
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…
- Greedy change-making with British coins always gives the fewest coins, and with the coin set {1, 15, 20} it…
- Sort each problem by whether the greedy approach is provably optimal or can fail.