[math-fun] four coin changing
Three integer coin values 1 < a < b will make optimal (smallest number of coins) change for all amounts using the greedy ("pick the largest possible coin first") algorithm if and only if there is an integer m so that Floor[b/m] = a. For example: A) The penny=1, nickel=a=5, dime=b=10 has m=2; but B) If the coin set 1, 3, 4 the greedy algorithm uses three coins to make change for 6 = 4 + 1+ 1 cents using the greedy algorithm, while the non-greedy choice 3+3 uses fewer coins. There is no integer m such that Floor[4/m] = 3. Is there a similar criterion for four coins 1 < a < b < c? Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm
On Thursday, June 5, 2003, at 10:38 AM, Thane Plambeck wrote:
Three integer coin values 1 < a < b will make optimal (smallest number of coins) change for all amounts using the greedy ("pick the largest possible coin first") algorithm if and only if there is an integer m so that Floor[b/m] = a. [...] Is there a similar criterion for four coins 1 < a < b < c?
I have no idea, but I'll mention (in case you didn't already know) that there is a polynomial-time algorithm that determines whether an arbitrary system of denominations has the property that the greedy algorithm is always optional. See Jeff Shallit's article "What This Country Needs is an 18-cent Piece" in the most recent Mathematical Intelligencer, available from his web page, http://www.math.uwaterloo.ca/~shallit/papers.html Actually, looking at the algorithm, the answer to your question is probably "yes", though it won't be quite as simple as for 3 coins, but I don't have the time to think this through right now. --Michael Kleber kleber@brandeis.edu
participants (2)
-
Michael Kleber -
Thane Plambeck