# For what coinage systems does a greedy algorithm not work in providing change?

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?

-
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
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
@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

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$.