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

  • 1
    "Coin change .... greedy ..." -- *Vader NOOOOoooo* – Raphael Nov 22 '15 at 8:38
  • 3
    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.

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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