This is a question regarding the common version of the Change making problem, which is:
"how can a given amount of money be made with the least number of coins of given denominations (we have infinite copies of each coin)"
Specifically, regarding determining whether a given coin system is canonical (canonical = greedy approach is always best). The paper by Pearson A Polynomial-Time Algorithm for the Change-Making Problem provides a polynomial-time, O(n^3) algorithm for doing so, which from what I've gathered is the best to date.
However, sadly, I just for the life of me cannot understand what that algorithm actually is from reading this paper, due to the very formal language used.
My question is of the "simple but not easy" variety – Could I ask you fine folks to give me a simple "real" example of how Pearson's algorithm works? Let's take a simple non-canonical coin set – 1, 2, 4, 5 or 1, 2, 3, 6, 17, 21 (whichever is more instructive). How exactly does one run the Pearson check with these specific values? Thanks in advance for taking the time.
Best Answer
Theorem $1$ in the paper gives an algorithm for constructing $O(n^2)$ possible minimal counterexamples to the assertion that the system is canonical. Each of these can be tested in linear time. If none of the potential counterexamples is in fact a counterexample, then there is no counterexample, and the system is canonical.
Consider the coin system $$21,17,6,3,2,1$$ with $6$ denominations. For each choice of integers $1<i\leq j \leq n$ the algorithm constructs a potential counterexample. Number the coins in decreasing order, so that $c_1=21,\dots, c_6=1$. First, we construct the greedy representation of $c_{i-1}-1$. So, if $i=2$, we construct the greedy representation of $c_1-1=20$, which the paper calls $G(20)$. $$G(20)=(0,1,0,1,0,0)$$ meaning that we use one coin of value $17$ and one of value $3$.
Let's say that $j=3$. Theorem $1$ says that a potential minimal counterexample agrees with $G(20)$ in positions $1$ through $j-1$, is $1$ more in position $j$ and $0$ elsewhere. That is $$M(w)=(0,1,1,0,0,0)$$ This is a representation of $23$ $(17+6)$. The greedy representation of $23$ is $(1,0,0,0,1,0)$ $(21+2)$. Both representations have size $2$, so $23$ is not the minimal counterexample.
On the other hand, let's keep $i=2$ and try $j=2$. Theorem $1$ gives us $$M(w)=(0,2,0,0,0,0)$$ which is a representation of $34$ of size $2$. The greedy representation of $34$ is $$(1,0,2,0,0,1)$$ of size $4$, so the system is not canonical, and $34$ is the minimal counterexample.
CLARIFICATION
Since there have been a couple of questions about it, I should explain that $i$ and $j$ represent the first and last non-zero positions in the minimal counterexample $M(w)$, so that we must have $i\leq j$.