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"
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.
There are two reasonable versions of what "optimal change" could mean---one where the change only passes from seller to buyer, the other where it goes both ways as in paying $1.00 + .02 and receiving back $.25 to make a $.77 purchase. In the second version, greedy isn't optimal. For either version, there there is a finite-state automaton that will tell which sequences are optimal, where optimal is defined as the fewest coins and least in some sorting order, e.g. the biggest first. There's also an algorithm that will produce this finite state automaton. This is a special case of a more general theory for automatic groups----there is a similar procedure to produce finite-set-automata associated with any set of generators of any word-hyperbolic group. There is a set of programs "kbmag" by Derek Holt at the University of Warwick, that will start from generators and relators (not hard to produce in this situation) and produce finite state automata, but this is overkill --- in any practical situation you can work out the FSA by hand. I haven't done it, but I'd recommend trying it for your (10,6,1). You could first think of a picture on a lattice in 3 dimensions where you map N + N + N -> N (N = natural numbers) via (10,6,1) and mark what numbers correspond to what lattice points. --Bill Thurston On May 4, 2005, at 9:25 AM, David Wilson 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
Again, I was hiding my ulterior motive, which was to count the subsets of donominations {1,...,n} that were greedy-optimal. Bill Thurston remarked that there was an FA algorithm that might help me with this, but that I would have to work out FA by hand for each set of denominations. Since I would be considering a large number of denominations sets, I don't think the manual method is practical. II think I'll try the algorithm given in Shallit reference. ----- Original Message ----- From: "William P. Thurston" <wpthurston@mac.com> To: <ham>; "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, May 04, 2005 10:09 AM Subject: Re: [math-fun] Greedy Change
There are two reasonable versions of what "optimal change" could mean---one where the change only passes from seller to buyer, the other where it goes both ways as in paying $1.00 + .02 and receiving back $.25 to make a $.77 purchase. In the second version, greedy isn't optimal.
For either version, there there is a finite-state automaton that will tell which sequences are optimal, where optimal is defined as the fewest coins and least in some sorting order, e.g. the biggest first. There's also an algorithm that will produce this finite state automaton. This is a special case of a more general theory for automatic groups----there is a similar procedure to produce finite-set-automata associated with any set of generators of any word-hyperbolic group. There is a set of programs "kbmag" by Derek Holt at the University of Warwick, that will start from generators and relators (not hard to produce in this situation) and produce finite state automata, but this is overkill --- in any practical situation you can work out the FSA by hand. I haven't done it, but I'd recommend trying it for your (10,6,1). You could first think of a picture on a lattice in 3 dimensions where you map N + N + N -> N (N = natural numbers) via (10,6,1) and mark what numbers correspond to what lattice points. --Bill Thurston
On May 4, 2005, at 9:25 AM, David Wilson 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
About 15 years ago I posed a problem in the American Math Monthyly about finding the number of {1,a,b} triplets that make optimal change (you can read the exact problem statement here) http://www.plambeck.org/oldhtml/mathematics/coinchanging/coinchangingproblem... I've tried more than once to work out the corresponding four coin asymptotics {1,a,b,c} without success Thane Plambeck http://www.plambeck.org/ehome.htm David Wilson wrote:
Again, I was hiding my ulterior motive, which was to count the subsets of donominations {1,...,n} that were greedy-optimal.
Bill Thurston remarked that there was an FA algorithm that might help me with this, but that I would have to work out FA by hand for each set of denominations. Since I would be considering a large number of denominations sets, I don't think the manual method is practical.
II think I'll try the algorithm given in Shallit reference.
----- Original Message ----- From: "William P. Thurston" <wpthurston@mac.com> To: <ham>; "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, May 04, 2005 10:09 AM Subject: Re: [math-fun] Greedy Change
There are two reasonable versions of what "optimal change" could mean---one where the change only passes from seller to buyer, the other where it goes both ways as in paying $1.00 + .02 and receiving back $.25 to make a $.77 purchase. In the second version, greedy isn't optimal.
For either version, there there is a finite-state automaton that will tell which sequences are optimal, where optimal is defined as the fewest coins and least in some sorting order, e.g. the biggest first. There's also an algorithm that will produce this finite state automaton. This is a special case of a more general theory for automatic groups----there is a similar procedure to produce finite-set-automata associated with any set of generators of any word-hyperbolic group. There is a set of programs "kbmag" by Derek Holt at the University of Warwick, that will start from generators and relators (not hard to produce in this situation) and produce finite state automata, but this is overkill --- in any practical situation you can work out the FSA by hand. I haven't done it, but I'd recommend trying it for your (10,6,1). You could first think of a picture on a lattice in 3 dimensions where you map N + N + N -> N (N = natural numbers) via (10,6,1) and mark what numbers correspond to what lattice points. --Bill Thurston
On May 4, 2005, at 9:25 AM, David Wilson 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
David Wilson -
Michael Kleber -
Thane Plambeck -
William P. Thurston