# Coin Change Problem(Greedy Algorithm)

In Coin Change Problem, if the ratio of Coin Value ($\frac{Coin_(i+1)}{coin(i)}$) is always increasing then we can use Greedy Algorithm?

Example- $(1,3,4)$ are denominations of coin. If I want to pay $Rs.6$ then the smallest coin set would be $(3,3)$. This solution set cannot be found by greedy Algorithm because it does not satisfy $(\frac{4}{3} > \frac{3}{1})$.

• "Coin change .... greedy ..." -- *Vader NOOOOoooo* – Raphael Nov 22 '15 at 8:38
• Try simultaneously proving your claim and looking for a counterexample. Get back to us if you haven't succeeded after trying for a few hours. – Yuval Filmus Nov 22 '15 at 12:58
• By the way, the Wikipedia article on the problem is far from good, but it does contain some information. – Raphael Nov 23 '15 at 19:14
• @YuvalFilmus I did try but count not prove it.Can you help. – Dhrub Kumar Feb 28 '16 at 12:27

For the set of coins (2,3,11). $\frac{3}{2}<\frac{11}{3}$ so by your assumption we can be greedy here. Consider the value of 23. The greedy strategy would involve first taking 2 11 cent coins to give us 22 cents. Then there is nowhere left to go, we cant possibly get to 23 from here. We do have a solution though with $(0,4,1)$
Say, set of coin = {1, 10, 25}
It doesn't satisfy 25/10 > 10/1 But still can be solved by greedy algorithm.
Now, say X is any set of coins in increasing order. Then, for all a and b in X where a < b, if 2*a <= b satisfies, It will be solvable with greedy algorithm.