1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

The greedy algorithm here is optimal. Obviously, if there are two $5$ coins, then this is sub-optimal by replacing with $10$. Similarly, one should replace two $1$s with a $2$, and replace three $2$s with one $5$ and one $1$. Hence there is at most one $1$, at most two $2$s, and at most one $5$. Furthermore, if there are two $2$s and one $1$, then this is sub-optimal by replacing with $5$.

It can be seen that these values are the ones given by the greedy algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.