Greed can fail for American money
You all know the change-making problem, right? The task is to represent a given amount of money in a given system of coins, using as few coins as possible. The greedy algorithm makes change by repeatedly subtracting the largest available coin from the remaining amount, and is optimal for most actual systems of coins but not in general. It makes a good example problem for algorithms classes, because it's easy to understand and helps with two important goals of the class: convincing the students that greedy algorithms aren't always the right way to solve problems, and giving them a simple example of dynamic programming. When I've presented this problem to my algorithms classes I've usually made up a fictitious coin system with unusual denominations (e.g. large prime numbers) to force non-greediness, but today I encountered a very natural non-greedy example.
An easy way to make a coinage system for which the greedy algorithm always works is to make each coin be an integer multiple of the next smaller coin, but there can be systems of coins for which greed is optimal that are not constructed in this way, and the U.S. coinage system is a good example. It uses dollars (100c), half-dollars (50c), quarters (25c), dimes (10c), nickels (5c), and pennies (1c), but the dollars and half-dollars are rarely used. Or, one could consider the paper money (100c, 200c, 500c, 1000c, 2000c, and 5000c, with 200c being rare) to also be part of the system. With or without the paper money and rare denominations, the greedy algorithm is optimal, despite the non-integer ratio between quarters and dimes.
But when buying my lunch today, I needed 40 cents in change, and the cash register was out of nickels. That is, due to the outage, I was using a system where the denominations are (25,10,1). If one makes change greedily, the solution uses seven coins (quarter, dime, and five pennies) but a better non-greedy solution uses only four dimes. My cashier stood for a while with a quarter in his hand, taking out dimes and putting them back, before finally figuring out what to do and giving me the optimal change.
A variant I haven't seen formalized (but that I have seen in my own interactions with cashiers): two people want to convey a given amount of money from one person to another so that the total number of coins that change hands in either direction is minimized. How do they do it? Again, there's a straightforward dynamic programming solution, but maybe (as for change making) there's a simpler greedy-like strategy that works for most common coin systems.
Comments:
2009-07-27T23:56:08Z
Looks like the general idea there is that the greedy strategy can fail when the number of coins required to make the amount (coini mod coini-1) is greater than some N for some i, where coini is the value of coin i.
Is N always 1, or can we place stricter bounds on it? If so, what are they?
Also, is this condition more accurately phrased as (k coini mod coini-1) > Nk -- and, if so, is Nk actually a function of k?
2009-07-28T00:03:56Z
See the paper Chang and Korsh linked from the comments of my previous post on the problem: {1,a,b} with a < b is greedy if and only if a ≤ (b mod a) + floor(b/a). I'm not sure offhand how this translates into the sort of formulation you describe, though, and I don't remember what happens for more than three coins.
2009-07-28T00:30:26Z
Hmm. I'm a bit confused, and expect I've got something wrong.
Suppose we vary your case slightly, and let a=10 and b=30. Then (b mod a) = 0, and floor(b/a) = 3. The algorithm then asks whether 10 is less than or equal to three, and concludes that a greedy algorithm doesn't apply -- which I think is obviously wrong.
Does the rule only apply when (b mod a) is nonzero?
2009-07-28T01:10:22Z
I think the condition that b mod a ≠ 0 is necessary for the formula to be right. Here's an explanation of where the formula comes from: by the JACM paper's results, one needs only to look at how the greedy and optimal algorithms make change for the smallest multiple of a that's greater than or equal to b. The greedy algorithm uses 1 + a - (b mod a) coins, except when b mod a = 0 in which case it uses only 1 coin. The optimal algorithm uses ceiling(b/a) coins, and (again except when b mod a = 0) this equals 1 + floor(b/a). So the two 1+ parts cancel and you're left with the inequality I gave. But it breaks down at two different points when b mod a = 0, in which case greed is always good.
2009-08-04T18:57:38Z
http://www.acoin.com/regular.htm
U.S. coinage at one time or another included half-cents, 2-cent pieces, 3-cent pieces, silver half-dimes, 20 cents Seated Liberty, silver dollars, 2 1/2 Dollars , 3 dollars, 4 dollars, 5 dollars, 10 dollars, 20 dollars. My maternal grandfather had each of these, but had to sell his entire coin collection when he was screwed on medical insurance and had to pay cash to stay alive.
-- Prof. Jonathan Vos Post
2009-08-11T04:18:24Z
Interesting. It makes me wonder which combinations existed concurrently and whether they were all optimally solved by the greedy algorithm.