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

Solution 1:

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