Clinton A Staley
Copyright 2011, Software Inventions, Inc
This is one of the lectures in our greedy algorithms series. You should already have read the introductory lecture on greedy algorithms and the example scheduling algorithm. We'll assume understanding of greedy algorithms and the greedy proof pattern in this lecture, but we'll introduce a rather different example of these, to show how they vary depending on the problem.
Our problem in this lecture is to find a way to make change for a certain number of cents, with the fewest possible coins. We'll use US coinage as our starting example, with 50, 25, 10, 5, and 1 cent pieces. (For any non-US users of this doc, that's a half-dollar, quarter, dime, nickel and penny, terms we'll use in the following discussion.) The problem doesn't require US coinage, of course. Any coin set may be analyzed, so long as it at least includes a 1-cent (or 1-unit) coin, so you can get totals to1-cent accuracy. As we'll see, however, the elegant greedy algorithm for this problem only works with certain coin sets.
OK, so from prior lectures we know the right way to start on a problem like this is to try out some concrete examples to gain intuition. So, let's make change for 97 cents, with the fewest possible coins.
Or rather, you make change for 97 cents, using only 6 coins.
You should come up with 50, 25, 10, 10, 1, 1. There's no other way, in fact, to get 6 coins for that amount in US coinage.
But, US coinage is so boring. Let's try something exotic.
Make change for 156 cents in a coinage with denominations 81, 27, 9, and 3, and 1, using 6 coins. (No dollar bills.) And, for extra credit, conversion to this particular coin denomination set is mathematicallly identical to doing what numerical translation?)
You should come up with 81, 27, 27, 9, 9, 3. And there's no other way to do this. (The extra credit answer is that this is really equivalent to asking how to write 156 in base 3, since the coin values correspond to base 3 place values.)
And, the base 3 analogy, while it doesn't apply to all coin sets, does give us some hint as to what a suitable greedy algorithm might be.
Based on what you tried for the prior two problems, propose a greedy algorithm for finding change with minimal coins
You might have come up with the simple rule: pick the largest coin each time. Or, more exactly, "Pick the largest coin that is no larger than the remaining change you need to make". So, for instance, if we start with 97 cents, then a halfdollar is the largest coin we could use, so we do that, and are left with 47 cents. Now a quarter is the largest we could use, so we add a quarter, and are left with 22 cents. Next it's a dime, leaving 12 cents, and a dime again, leaving 2 cents. (There was never a case where we needed to use a nickel in this example), Add the remaining two cents, and we're done.
So, it works for US coins in that case. And when you think about it, it pretty much has to work for the base-3 coin set, since in any base you count up in the highest digit first, and then use smaller digits to get more accuracy.
But, that's just two coin sets and two concrete examples. How sure are we that this works in general? Well, next step is to try to find counterexamples. Let's focus on the US coin set.
Can you come up with an amount of change for US coins, for which this pick-the-largest-coin-possible algorithm will fail to produce a minimum-coin solution?
Nope, you can't. So, at least for US coins, this appears to work.
Let's prove that it does, at least for the US coin case. We'll follow the greedy proof steps:
1. Assume that choosing the highest value coin doesn't actually always work. This implies that for some number of cents there's a solution S that doesn't start with the highest value coin possible, and is better than our greedy solution.. Perhaps the cents are greater than or equal to 50, but S doesn't use a half dollar, or greater than or equal to 25 but less than 50, and S doesn't use a quarter.
2. So, now we need to show that S can be converted into an equally good, or even better solution by adjusting S so that it makes a greedy choice. Hmm. OK, well let's once again try a concrete example for starters. Say we want 19 cents, but our alternate solution S doesn't use a dime. Could be 5, 5, 5, 1, 1, 1, 1, for instance. But, in that case, can't we replace two of the nickels with a dime, thus converting this into a greedy-choice solution: 10,5, 1, 1, 1, 1?
OK, but does that work regardless of the amount? Turns out it does, though in some cases it's a little tricky. WLOG, let's assume the solution S has its coins in descending order, like I listed them above. (What's "WLOG", you ask? It's a new vocabulary term! Without Loss Of Generality – something you'll see in a lot of proofs when you make a specification that doesn't actually restrict the relevance or generality of the proof.)
So, if the greedy solution should use a dime, but S, our proposed nongreedy alternate, doesn't, then S will have some number of nickels and pennies, in nickel/penny order (e.g 5, 1, 1, 1, 1, 1 or 5, 5, 1, or even just pure pennies). If you think about it, assuming you have at least 10 cents, you can always grab an even 10 cents worth of coins from the start of that sequence and replace it with a dime, reducing the total number of coins. If S starts with two nickels, convert them to a dime. If it starts with only one nickel, and then pennies, convert the nickel and the first five pennies into a dime. If it's only pennies, then convert the first 10 pennies into a dime. So, any solution S that doesn't use a dime can be converted into one that does.
A similar line of reasoning works if the greedy choice would choose a nickel (which it would for cent-amounts between 5 and 9, inclusive).
But what about the case for a quarter? That's a little harder. If the greedy choice would pick a quarter, which it would if the total was between 25 and 49, inclusive, and S doesn't use a quarter, then S uses dimes, nickels and/or pennies instead. Now, if S has no dimes, then it's all nickels and/or pennies, and we can take the first 25 cents worth of those and convert them to a quarter, leaving us with a quarter, and perhaps some leftover nickels and pennies. Likewise if it has two or fewer dimes, followed by nickels and pennies, then we grab the one or two dimes, plus some more nickels and/or pennies, and turn that into a quarter, again turning S into a greedy-choice solution.
But, what if S has three more dimes? Maybe we're talking 40 cents, and S is 10 10 10 10. Well, in this case we can take the first three dimes, and replace them with a quarter and a nickel. That's removing three coins and adding 2, so the modified version is even better, and it uses a greedy choice.
OK, so finish out the proof for half-dollars. Here, you should find that most cases are pretty easy, but there is still one S possbility that requires slightly cleverer reasoning similar to our quarter vs 3+ dimes case. In particular, you should find one S case, starting with 4 particular coins, that needs special handling.
If there are no quarters, or two quarters, then S can easily be adapted to use a half dollar. If it's 25, 25 ... then just replace the first two quarters with a halfdollar. If it's all dimes nickels pennies, then just replace the first 50-cent's worth of dimes, nickels and pennies. 10, 5, and 1 all divide evenly into 50.
Even with just one quarter, it's still straight forward if there are only one or two dimes. Take the quarter, the dime(s) and a nickel or 5 pennies, and turn them into a halfdollar. But, if S starts with 25, 10, 10, 10, ... Then, and only then, we cannot cut an even 50 cents off the start of S. Instead, we'll take the first 55 cents, 4 coins in all, and replace them with 50, 5 – 2 coins. And again we can alter S to at least as good a solution using the greedy choice.
So, we're finally at step 3 of the greedy proof. All possible cases where a solution S starts with a nongreedy choice have been shown to be convertible to cases where we do start with a greedy choice, and the modified solution is at least as good. There can be no non-greedy-choice solution that is better than a greedy choice solution.
No, it doesn't. Here's an example. Make change for 40 cents with a coin set 25 20 5 1.
What does the greedy algorithm choose for this case, and what alternate solution is better?
Greedy algorithm chooses 25 5 5 5, while 20 20 is possible.
OK, so why didn't it work? Didn't we just prove it did? Well, we proved it did for US coins. Our entire proof was based on US coins. But, with this coin set, the alternate solution S could begin with 20, 20, and there is no way to remove those two and replace them with a quarter, without also using 3 nickels, and coming up with a weaker solution, so the proof breaks down.
OK, so come up with two more coin sets for which the greedy approach can be proven correct, and two for which it cannot.
There are a lot of possibilities of course, but here are a couple for which the greedy approach works:
64 32 16 8 4 2 1
25 15 5 3 1
The first is just a binary analog of our 81, 27, 9, 1 case from earlier. The second is more complex, but even if you have S solutions that start, say, with 15 15, that can be replaced by 25 5. Or a start with 3 3 can be replaced with 5 1.
For cases that don't work, try:
30 20 5 1
or if you want a weird one
50 25 11 7 1
Find S solutions, identifying their starting coins, for which the greedy proof breaks down for those last two coinsets.
For 30 20 5 1:
For 50 25 11 7 1:
OK, but I see a problem with the supposedly good case of coin set 25 15 5 3 1. The greedy proof works, but clearly for 30 cents, the nongreedy S solution of 15 15 is as good as the greedy solution of 25 5. What's wrong?
Nothing's wrong. We aren't proving that the greedy approach picks the best solution (unless there's only one best solution). The proof is totally geared toward proving that the greedy approach chooses a best solution – that no alternate approach is better, since all can be converted to an at least as good a greedy alternative, but that doesn't preclude the possibility that some alternate choice is just as good, and that may often be true.
Change making is a classic greedy algorithm example, and you can find many web resources on it if you would like supplemental material. (A Google hunt on "change making algorithm" will get you a torrent of pages on the subject.) Per usual, of course, answer all questions without web assistance.
So, there's our change-making greedy algorithm. Summary of major ideas:
1. An alternative greedy algorithm and proof.
2. A more subtle, multi-case proof, than the one for scheduling.
A. For which of these coin sets does the greedy algorithm work? Either prove that they do, or give the lowest value for which they will fail.
50 20 10 2 1
10 7 3 1
11 7 3 1
11 8 3 1
B. Add one coin value X that will make this set work for the greedy algorithm. Find a different one Y that will also make it work.
30 7 1
For A: The first and third are OK, but second and fourth fail on 14 and 16, respectively.
For B: You need a 2, 3 or 4, or the case 35 will fail. 7 7 7 7 7 would beat 30 1 1 1 1 1.