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?
Best Answer
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$.