11
$\begingroup$

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?

  • 0
    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).2012-02-06
  • 0
    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.2012-02-06
  • 7
    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. (http://dx.doi.org/10.1016/j.ejc.2009.05.002)2012-02-06
  • 0
    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.2012-02-06
  • 0
    On second thought, just to show a counterexample to my original notion, consider if you have the coin set values {1, 9, 11} and you want 18 cents in change. Then the solution with the smallest number of coins is {9, 9} whereas a greedy algorithm would give {11, 1, 1, 1, 1, 1, 1, 1}.2012-02-06
  • 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.2012-02-07
  • 0
    possible duplicate of [Looking to understand the rationale for money denomination](http://math.stackexchange.com/questions/25209/looking-to-understand-the-rationale-for-money-denomination)2012-11-12

1 Answers 1

0

Intuitively, the requirement for the greedy algorithm to work for a coinset $c_1 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$.