Consider the standard greedy algorithm for making change. Namely, give the user
ID: 3888703 • 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
Normally greedy algorithm fails in cases like following:
For example: V = {1, 3, 4} and making change for 6: Greedy gives 4 + 1 + 1 = 3 Dynamic gives 3 + 3 = 2
Therefore, greedy algorithms are a subset of dynamic programming. Technically greedy algorithms require optimal substructure AND the greedy choice while dynamic programming only requires optimal substructure.
It is true that,if every coin is at least twice as valuable as the next smaller coin, this greedy algorithm always provides optimal change.
Example: For coin denominations 1, 5, 10, the algorithm does give the optimal solution.
Proof: Consider any optimal solution. That solution cannot have
– more than four 1’s (as five 1’s could be replaced by one 5), or
– more than one 5 (as two 5’s could be replaced by one 10).
Thus, the number of 10s in both greedy algorithm and optimal algorithm must be same, and the value of rest of the coins adds up to at most 9.
In a similar way, it can be proved for any given denomination where every coin is at least twice as valuable as the next smaller coin.