Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins.

However, for a coinage system with 12 cent coins, a greedy algorithm would not work. For instance, change for 15 cents would be a 12 cent coin and 3 pennies (4 coins total) whereas a dime and a nickel (2 coins) would be optimal.

In what types of coinage systems does the greedy algorithm not work?

share|improve this question
    
Maybe a system where the values are relatively prime, plus some pennies? For example, if you have 1c, 3c and 4c (gcd(3,4) = 1) then the greedy algorithm for 6c would not work (4 + 1 + 1 is worse than 3 + 3). Or if you have 1c, 5c and 7c then it won't work for 10c (7 + 1 + 1 + 1 worse than 5 + 5). –  Sp3000 Feb 6 '12 at 14:36
    
I suspect you need each coin to be at least twice the value of the next smaller coin. Certainly, it must be at least twice the value of the next smaller coin minus 1. –  Thomas Andrews Feb 6 '12 at 14:56
6  
Here's a paper that summarizes some of what's known about this problem: A. Adamaszeka and M. Adamaszek, "Combinatorics of the change-making problem", European Journal of Combinatorics, Volume 31, Issue 1, January 2010, Pages 47–63. (dx.doi.org/10.1016/j.ejc.2009.05.002) –  Chris Phan Feb 6 '12 at 15:18
    
I haven't done much to verify this, but I think one notion would be that you don't want two coins of lesser value for which the sum of their values is greater than the value of the next coin. So in your example, you have the nickel, the dime, and the 12-cent piece, but the value of the nickel plus the value of the dime is greater than the value of the 12-cent piece. Notice that this never happens in the United States coinage system. –  Kurtis Zimmerman Feb 6 '12 at 15:23
3  
@ChrisPhan, I think you should make that an answer, especially if you'd care to include one or two of the more useful results from that paper. –  Gerry Myerson Feb 7 '12 at 0:10
show 2 more comments

1 Answer

up vote 0 down vote accepted

Intuitively, the requirement for the greedy algorithm to work for a coinset $c_1<c_2<...<c_n$ is that for any valid amount $v \in [c_i,c_{i+1}[$ the smallest solution for $v-c_i$ is smaller by 1 than the smallest solution for $v$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.