2
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
13
  • $\begingroup$ I know this. My question is what the author wanted to prove in their ad hoc proof for the Euro coins only. $\endgroup$
    – herophant
    Jul 10, 2019 at 11:53
  • $\begingroup$ I was pointing out that your counter-example does not contradict the author. However, if, only using coins smaller than $x$, you can't create an optimal sum whose value is $\geq x$, then the greedy algorithm is optimal. Indeed, if from a total $N$ you take off the biggest coin possible, as you cannot remove that quantity using a smaller number of coin (by the virtue of the previous remark), then you are ensure to use the smallest numbers of coins. $\endgroup$
    – Florian Ingels
    Jul 10, 2019 at 12:01
  • $\begingroup$ "However, if, only using coins smaller than x, you can't create an optimal sum whose value is ≥x, then the greedy algorithm is optimal." Can you edit your answer to show why this is true? $\endgroup$
    – herophant
    Jul 10, 2019 at 12:03
  • 1
    $\begingroup$ Because that means that if the sum is at least $x$, the optimum solution must contain $x$, which is the greedy algorithm. $\endgroup$
    – saulspatz
    Jul 10, 2019 at 13:29
  • $\begingroup$ @saulspatz I fail to see why this is true... Consider the euro coins described in the problem. Say x = 5. 2+2+1 = 5. Here we used coins smaller than x to create something $ \geq x$, since we are not allowed to use $x=5$ in the condition that I quoted form Florian. By this condition, the greedy algorithm should not apply in this case, which is obviously false since it does for Euros. $\endgroup$
    – herophant
    Jul 10, 2019 at 14:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .