A canonical coin system is defined as one where the greedy algorithm is the optimum algorithm for the change-making problem ().
What can I do to build a "canonical" coin system without just checking all possible outputs?
Is it that each coin is a multiple of some other number? Or that no coin is larger than a certain ratio of a smaller coin?
$\endgroup$ 11 Answer
$\begingroup$A result$^1$ by B. N. Tien and T. C. Hu (“Error Bounds and the Applicability of the Greedy Solution to the Coin-Changing Problem,” Operations Reseach, 23(3):404-418, 1977) may be helpful: In order to decide whether the coin system $c_1=1<c_2<c_3<\ldots$ is canonical, it suffices to check only for each $m$ whether the greedy solution for $\lceil\frac{c_{m+1}}{c_m}\rceil c_m$ is optimal.
$^1$ The actual theorem I found quoted in arXiv:0809.0400 reads
$\endgroup$Theorem 2: Let $\$_1 = \langle 1, c_2 , \ldots , c_m\rangle$ and $\$_2 = \langle 1, c_2 , \ldots , c_m, c_{m+1}\rangle$ be two coin systems such that $\$_1$ is canonical but $\$_ 2$ is not. Then there is some $k$ such that $k·c_m < c_{ m+1} < (k+1)·c_m$ and $(k+1)·c_m$ is a counterexample of $\$_2$.
