Algorithms and Data Structures · Middle · Question 43 of 75
Why can a greedy algorithm fail for making change with coins [1, 3, 4] and amount 6?
- ✓Correct answer: Greedy takes 4 + 1 + 1 (three coins), while 3 + 3 uses only two
- 2Greedy can't handle amounts larger than the biggest coin
- 3Greedy always fails when coins are not powers of two
Explanation
Taking the largest coin first is optimal for standard currencies but not for arbitrary coin sets. Dynamic programming over amounts (dp[a] = 1 + min dp[a - coin]) always finds the minimum.