Consider the standard greedy algorithm for making change. Namely, give the user
ID: 3888169 • Letter: C
Question
Consider the standard greedy algorithm for making change. Namely, give the user change by giving them as many as possible of the highest denomination coin or bill, then as many as possible of the next highest coin or bill, etc. We know that this will always give correct change (assuming that there is a 1-“cent” coin defined). We also know that for some sets of coins (such as American coins) it’s an optimal algorithm, in the sense that it minimizes the total number of coins given out. But we know that there are some cases (classic British coins, as in the in-class exercise #2) for which it doesn’t work. It has been hypothesized by some students that if every coin is at least twice as valuable as the next smaller coin, this greedy algorithm always provides optimal change (again, assuming the existence of a 1-“cent” piece).
Either show that this is true by outlining a proof that the greedy choice and optimal substructure properties hold, or prove that it isn’t true in general by giving a single counterexample.
Explanation / Answer
The given proposition is false. The coins let 1,3,7,16, this satisfies the condition that every coin is atleast twice as valuable as the next smallest coin. If we making change for 21, the greedy solution will give 16,3,1,1. But the optiomal solution is 7,7,7.