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