I think Jeff Shallit is on math-fun, in which case I'm stealing his fire by answering. Jeff's article "What This Country Needs is an 18-cent Piece", in (my & Ravi's Entertainments column in :-) Mathematical Intelligencer 25 #2 (spring 2003), is a great exposition of what's known. In brief: Remarkably, there *is* a good algorithm for determining whether the greedy algorithm always produces optimal results with a given set of coins. It appeared in [D. Pearson, "A polynomial-time algorithm for the change-making problem", Technical Report TR 94-1433, Department of Computer Science, Cornell University, June 1994]. The reason I say it's remarkable is that, on the other hand, Kozen and Zaks proved that determining whether a given set of coins is greedily optimal for a *particular* amound of change is actually NP-hard! As Jeff's article explains, it turns out that if the greedy algorithm with some set of coins is ever non-optimal, then the minimum amount of change for which it performs non-optimally can be characterized and tested for nicely. If you don't have a copy of our most excellent publication to hand, you can find the paper (and links to lots of press that it generated) at: http://www.cs.uwaterloo.ca/~shallit/papers.html --Michael Kleber On 5/4/05, David Wilson <davidwwilson@comcast.net> wrote:
I understand that with US coins of denominations (100, 50, 25, 10, 5, 1) cents, making change by the greedy algorithm (at each step select the largest possible coin) leads to optimal change (fewest coins) for all amounts.
There are other conceivable sets of denominations, e.,g, (10, 6, 1), where the greedy algorithm fails (for example, the greedy algorithm gives 18 = 10+6+1+1 whereas 18 = 6+6+6 uses fewer coins).
Is there an algorithm for determining if a given set of coins gives optimal change via the greedy algorithm?
- David W. Wilson
"Truth is just truth -- You can't have opinions about the truth." - Peter Schickele, from P.D.Q. Bach's oratorio "The Seasonings"
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.