Greedy Algorithm & Optimal Coin Change

[CRGreathouse]

I'm not sure that this is the right place for this post, but I couldn't find a better.

Many years ago I considered the problem of making change with (say) quarters, dimes, nickels, and pennies. I tried to prove to myself that what I now call the greedy algorithm (pick the most valuable coin that doesn't take you over your limit) always made optimal change -- that no solutions with fewer coins existed. At the time I wasn't able to find a proof of the specific case {25, 10, 5, 1} but I could see that the general result failed -- consider {5, 4, 1} to make a total of 8 cents. The greedy algorithm gives (5, 1, 1, 1) but (4, 4) is better.

I was wondering if there's a good characterization of what combination of coin values make the greedy algorithm always optimal. Back then I could see that being in a geometric series was a sufficient, but unnecessary, condition. Briefly reconsidering the problem, it seems that the greedy algorithm should be optimal for superincreasing sequences -- but is this necessary for optimality? Any thoughts, counterexamples, or reading/references?

 

[Hurkyl]

This is certainly a classical problem. A quick search turns up this:

http://mathforum.org/wagon/spring04/p1009.html

(but I can't seem to follow the link contained in it. I don't think you could get the text easily from there anyways)

which makes it sound like a necessary and sufficient condition won't be simple to write. I know there are some nice, simple, sufficient conditions, but I can't remember the usual one, and I think my only hard reference is at work.


edit: I think this is the paper on it. (You can grab it from the "cached: ... PDF" link in the top-right corner) It doesn't seem terribly clear, but maybe I'm just tired.

 

[CRGreathouse]

edit: I think this is the paper on it. (You can grab it from the "cached: ... PDF" link in the top-right corner) It doesn't seem terribly clear, but maybe I'm just tired.

Thanks a bunch, that's exactly what I was hoping for I'll read through it and see how much I get. I appreciate it!

 

[CRGreathouse]

Well, I read the paper. It shows that it can be decided in polynomial time (O(n^2)) if a certain combination of coin values can always be solved optimally with the greedy algorithm, even though determining the least number of coins needed for a given set of coin values and total x is NP-hard.

Also, I was able to find a counterexample to my 'conjecture' above. Not all superincreasing sequences are solved optimally by the greedy algorithm; consider coins {2001, 1000, 1} and total 3000. I'll see if I can find the least superincreasing counterexample now -- clearly, it has exactly 3 coins.

Edit: I think it's {6, 4, 1} with a total of 8.