Greed can fail for American money

You all know the change-making problem, correct ? The undertaking is to represent a given measure 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 total, and is optimum for most actual systems of coins but not in general. It makes a good model problem for algorithm classes, because it ‘s easy to understand and helps with two important goals of the class : convincing the students that greedy algorithms are n’t constantly the right way to solve problems, and giving them a simpleton example of dynamic program. When I ‘ve presented this problem to my algorithm classes I ‘ve normally made up a fabricated coin arrangement with unusual denominations ( e.g. large premier numbers ) to force non-greediness, but nowadays I encountered a very natural non-greedy model .
An easily manner to make a neologism system for which the avid algorithm always works is to make each coin be an integer multiple of the future smaller coin, but there can be systems of coins for which greed is optimum that are not constructed in this way, and the U.S. neologism system is a good exemplar. 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 besides be part of the organization. With or without the composition money and rare denominations, the greedy algorithm is optimum, despite the non-integer ratio between quarters and dimes .
But when buying my lunch today, I needed 40 cents in variety, and the cash register was out of nickels. That is, ascribable to the outage, I was using a arrangement where the denominations are ( 25,10,1 ). If one makes change avariciously, the solution uses seven coins ( quarter, dime bag, and five pennies ) but a better non-greedy solution uses merely four dimes. My cashier stood for a while with a stern in his hand, taking out dimes and putting them back, before finally figuring out what to do and giving me the optimum exchange .
A variant I have n’t seen formalized ( but that I have seen in my own interactions with cashiers ) : two people want to convey a given total of money from one person to another then that the sum act of coins that change hands in either direction is minimized. How do they do it ? Again, there ‘s a aboveboard moral force scheduling solution, but possibly ( as for change make ) there ‘s a elementary greedy-like strategy that works for most common mint systems.

Comments:

brooksmoses: Some thoughts….
2009-07-27T23:56:08Z
: Some thoughts …. Looks like the general theme there is that the avid strategy can fail when the number of coins required to make the sum ( coin i mod coin i-1 ) is greater than some N for some i, where mint i is the value of coin i .
Is N always 1, or can we place stricter bounds on it ? If so, what are they ?
besides, is this condition more accurately phrased as ( k coin i mod coin i-1 ) > N k — and, if sol, is N k actually a function of k ?
11011110: Re: Some thoughts….
2009-07-28T00:03:56Z
See the paper : ra : Some thoughts …. See the composition Chang and Korsh linked from the comments of my previous station on the trouble : { 1, a, boron } with a < barn is avid if and lone if a ≤ ( boron mod a ) + floor ( b/a ). I 'm not certain offhand how this translates into the classify of formulation you describe, though, and I do n't remember what happens for more than three coins .brooksmoses: Re: Some thoughts….
2009-07-28T00:30:26Z
: rhenium : Some thoughts ….

Hmm. I ‘m a bit confused, and expect I ‘ve got something wrong .
Suppose we vary your subject slenderly, 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 peer to three, and concludes that a avaricious algorithm does n’t apply — which I think is obviously amiss .
Does the rule only practice when ( b mod a ) is nonzero ?
11011110 : re : Some thoughts ….
2009-07-28T01:10:22Z
I think the condition that b mod a ≠ 0 is necessary for the formula to be correct. hera ‘s an explanation of where the formula comes from : by the JACM composition ‘s results, one needs lone to look at how the greedy and optimum algorithms make change for the smallest multiple of a that ‘s greater than or equal to b. The avaricious algorithm uses 1 + a – ( b mod a ) coins, except when bel mod a = 0 in which case it uses only 1 mint. The optimum 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 bel mod a = 0, in which case greed is constantly good .
None: half-cents, 2-cent pieces, 3-cent pieces…
2009-08-04T18:57:38Z
http://www.acoin.com/regular.htm

: half-cents, 2-cent pieces, 3-cent pieces … hypertext transfer protocol : //www.acoin.com/regular.htm

U.S. neologism at one time or another admit half-cents, 2-cent pieces, 3-cent pieces, silver half-dimes, 20 cents Seated Liberty, ash grey dollars, 2 1/2 Dollars, 3 dollars, 4 dollars, 5 dollars, 10 dollars, 20 dollars. My enate grandfather had each of these, but had to sell his stallion coin solicitation when he was screwed on checkup indemnity and had to pay cash to stay alive .
— Prof. Jonathan Vos Post
11011110 : ra : half-cents, 2-cent pieces, 3-cent pieces …
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 .

source : https://ontopwiki.com
Category : Finance