# 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, 2015 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. Nov 22, 2015 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, 2015 at 19:14
• @YuvalFilmus I did try but count not prove it.Can you help. Feb 28, 2016 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)$

Check out Beck, "How to Change Coins, M&M's, or Chicken Nuggets: The Linear Diophantine Problem of Frobenius", pp. 6-74 in Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules, and Articles (MAA, 2009). Necessary and sufficient conditions for the greedy algorithm to work are given by Pearson, "A Polynomial-time Algorithm for the Change-Making Problem", TR94-1433, Department of Computer Science, Cornell (1994). They are much more complicated to check than your proposal.

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.

• This does not seem to answer the question and contains an unproven claim (last line).
– Raphael
Nov 23, 2015 at 19:15