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})$.
-
2$\begingroup$ "Coin change .... greedy ..." -- *Vader NOOOOoooo* $\endgroup$Raphael– Raphael2015年11月22日 08:38:25 +00:00Commented Nov 22, 2015 at 8:38
-
3$\begingroup$ 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. $\endgroup$Yuval Filmus– Yuval Filmus2015年11月22日 12:58:19 +00:00Commented Nov 22, 2015 at 12:58
-
$\begingroup$ By the way, the Wikipedia article on the problem is far from good, but it does contain some information. $\endgroup$Raphael– Raphael2015年11月23日 19:14:33 +00:00Commented Nov 23, 2015 at 19:14
-
$\begingroup$ @YuvalFilmus I did try but count not prove it.Can you help. $\endgroup$Dhrub Kumar– Dhrub Kumar2016年02月28日 12:27:42 +00:00Commented Feb 28, 2016 at 12:27
3 Answers 3
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.
-
3$\begingroup$ This does not seem to answer the question and contains an unproven claim (last line). $\endgroup$Raphael– Raphael2015年11月23日 19:15:30 +00:00Commented Nov 23, 2015 at 19:15
Explore related questions
See similar questions with these tags.