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

Question

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?

Answer 1

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

EDIT: As Martin De la Fuente pointed out, the above is incorrect. Unfortunately the system won't allow me to delete the accepted answer.

Answer 2

With thanks to Florian Ingels, here is a paper discussing this problem.

We can define a coinage system $C$ as being composed of an ascending series of coin denominations $\{c_i\}$ with $c_1=1$. If the greedy algorithm always works to deliver minimum number of any coins for every target value, it is canonical (in the paper's definition).

There are a number of useful rules of thumb that apply to most practically-encountered coinage systems.

Clearly any two-denomination system $\{1,c\}$ is canonical. Using as many high-denomination coins as possible gives the smallest coin count.

For a three denomination system $\{c_1=1,c_2,c_3\}$, any problem with the greedy algorithm has to occur between the two-coin solutions involving the biggest coin, $c_3+1$ and $c_3+c_2$. So if $c_2=2$ the greedy algorithm will always work.

We can separate the problem for a coinage system $C$ into distinct challenges if for a given denomination $c_k$ we have $c_k\mid c_j$ for all $j>k$; then the system is canonical if the two systems $C]_{c_k}=\{c_1,...,c_k\}$ and ${}_{c_k}[C = \{c_k/c_k=1, c_{k+1}/c_k,...,c_n/c_k\}$ are both canonical. So for the US coin system $U=\{1,5,10,25\}$ we can split into a cent-based coinage $U]_5 =\{1,5\}$ and a nickel-based coinage ${}_5[U = \{1,2,5\}$ both of which are canonical.

For the counterexample of $A=\{1,5,10,12,25\}$, no split is possible. The paper cited earlier gives that a non-canonical system will have some value that can be expressed in two coins that the greedy algorithm will use more coins for. Here as you identify, $5+10=15$ cents will have a wrong greedy solution of $12+1+1+1$.