how to prove the greedy solution to Coin change problem works for some cases where specific conditions hold
In the coin change problem, there is a given set of denominations $C = \{c_1, c_2, ... c_k\}$, and a non-negative value $ N $. We need to use a minimum number of coins to make $ N $.
A simple greedy algorithm, which chooses the largest denomination first, works only in some cases: $C = \{1, 5, 10, 25\}$ and any $N$.
But it fails for cases such as $C=\{1,15,25\}$ and $N=30$, in which it will pick 6 coins (one of 25's, and five of 1's) while the optimal is just two coins (two of 15's).
I wanted to prove (or disprove) that the greedy algorithm would work, if the set of coins $C$, when sorted satisfies that one coin is double or more the value than the previous.
i.e, if $C = \{c_1, c_2, ... c_k\}$, and after sorting in increasing order we get $C' = \{z_1, ... z_k\}$, then it should be that $2*z_i \le z_{i+1}$ $\forall i \in[1,k-1]\in Z$.
But I'm not sure how to proceed.
Edit: I think, it is safe to say that any N could be formed if a coin of denomination $1 \in C$ . I think this would make it a little simple, to assume that $C$ always has a $1$. (proof: choosing all 1's does give a solution. If any bigger coins could be chosen then the last remaining value could be formed by the 1's)
$\endgroup$2 Answers
$\begingroup$Consider coin denominations $1$, $4$, and $9$. This satisfies your criteria, since it includes $1$, and also $4\ge1+1$ and $9\ge4+4$.
The greedy algorithm would give $12=9+1+1+1$ but $12=4+4+4$ uses one fewer coin.
The usual criterion for the greedy algorithm to work is that each coin is divisible by the previous, but there may be cases where this is not so for which the greedy algorithm works anyway.
$\endgroup$ $\begingroup$make 15 cents.
given: 7 cent coins, 2 cent coins (7 is more than double the value of "2")
if you do greedy, 2 * 7 = 14 cents. cannot proceed further. Claim is false. qed.
Now, suppose c1=1. (this constraint was not specified in the problem but I suppose it is "natural"). However, the claim is STILL not true!
Make 50 cents given: 43 cent coins, 16 cent coins, 1 cent coins. (Clearly, we satisfy the "doubling" criteria")
Greedy Strategy: 1 * 43 cents + 7 * 1cent = 8 coins
Optimal Strategy: 3 * 16cents + 2 * 1cent = 5 coins
Claim is still false. qed.
People have written papers about the coin systems that can be optimally solved by greedy:
$\endgroup$
