I have four types of coins: 1, 2, 5 and 10. When I am given a number $k \in \mathbb{N}^{+}$, I have to return the least number of coins to reach that number. Using a greedy algorithm I can simply return all the possible 10 coins, and from the remaining, all possible 5 coins, and so on.
I need to proof that this greedy algorithm always return an optimal solution.
After some research, I realized this problem is called the coin-change problem and those coin systems that always return optimal solutions are called "canonical coin systems". Characterization of canonical coin systems has been made partially using theorems over specific subsets (1, 2, 3), but these theorems seems pretty hard to prove. Is there any simpler proof that I can use for this specific case of 1, 2, 5 and 10 without using those theorems?
For instance, the coinset 1, 5 and 10 can be easily proved to be canonical because every element is a factor of the larger elements. Can I use something similar in this case?
Best Answer
If you already know the proof as to why $S = \{1, 5, 10\}$ is canonical, then you can easily prove that $S' = \{1, 2, 5, 10\}$ is canonical. This is clearly true since, if $x$ never equals $2, 3,$ or $4$, then we never exercise our option to take the coin $2$, and we obtain an optimal solution due to the optimality of $S$. Conversely, if $x$ equals $2, 3,$ or $4$ at some point, then we can only do better by taking fewer coins since all of these cases reduce directly to either $0$ or $1$.