I'm reading Competitive Programmer’s Handbook. They take the Euro to perform analysis on a greedy algorithm.
For example, if the coins are the euro coins (in cents)
{1,2,5,10,20,50,100,200} and n (the sum we want to construct)= 520, we need at least four coins. The
optimal solution is to select coins 200+200+100+20 whose sum is 520.
Then the following explanation is given as to why this always works for euros:
First, each coin 1, 5, 10, 50 and 100 appears at most once in an
optimal solution, because if the solution would contain two such
coins, we could replace 57 them by one coin and obtain a better
solution. For example, if the solution would contain coins 5+5, we
could replace them by coin 10.In the same way, coins 2 and 20 appear at most twice in an optimal
solution, because we could replace coins 2+2+2 by coins 5+1 and coins
20+20+20 by coins 50 + 10. Moreover, an optimal solution cannot
contain coins 2 + 2 + 1 or 20+20+10, because we could replace them by
coins 5 and 50.Using these observations, we can show for each coin x that it is not
possible to optimally construct a sum x or any larger sum by only
using coins that are smaller than x. For example, if x = 100, the
largest optimal sum using the smaller coins is 50+20+20+5+2+2 = 99.
Thus, the greedy algorithm that always selects the largest coin
produces the optimal solution.
My question stems from the last paragraph. Just because we cannot find an optimal solution for x = 100, why is it the conclusion that the greedy algorithm is the best in this case?
Take the coin set {1, 3, 4}. There are no optimal solutions using smaller coins for 1 and 3, but for 4:
4 = 1+3
1+3 = 4 is an optimal solution because 1 and 3 cannot be replaced by some other coin (whereas 2+2+1 = 5 for euros). But this, to me does not justify greedy algorithm, and indeed it does not work in this case. (6 = 4 + 1 + 1 vs 3 + 3)
What is the argument that the author is trying to make in this case? Am I misunderstanding something?
Best Answer
The greedy algorithm is not optimal for any set of coins; it is optimal for the Euro coins sets.
Actually there is a definition of a canonical coin system that is, if the optimal solution of any change-making instance is the one returned by the greedy algorithm.
Please find some literature here : https://arxiv.org/pdf/0809.0400.pdf