2
$\begingroup$

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})$.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ "Coin change .... greedy ..." -- *Vader NOOOOoooo* $\endgroup$
    – Raphael ♦
    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
    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 ♦
    Nov 23, 2015 at 19:14
  • $\begingroup$ @YuvalFilmus I did try but count not prove it.Can you help. $\endgroup$
    – Dhrub Kumar
    Feb 28, 2016 at 12:27

3 Answers 3

Reset to default
4
$\begingroup$

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)$

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
-2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ This does not seem to answer the question and contains an unproven claim (last line). $\endgroup$
    – Raphael ♦
    Nov 23, 2015 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.