a) In the Coin changing problem, we have to give change for n rupees using the l

Question

a) In the Coin changing problem, we have to give change for n rupees using the least number of coins of a given set of denominations. It is clear that we cannot give change for any n for all set of denominations. For example, trivially, we cannot give change for 3, if no l, 2 or 3 rupees coins do not exist or not included in the allowed denominations. If the set of denominations include l ., then we can always give change, so that there is a way of changing n. for any n. We can use greedy approach to find the optimal solutions for many set of denominations. Show that, however, there are set of denominations for which we cannot find the optimal solution by greedy approach. You should include 1. in your denominations so that a solution always exists for the problem.

Explanation / Answer

Yes this can be proved..

For example, you want to find the change for 8 , and the coins you are having for change are 1 , 2 , 4 and 5 .

So, if we go by greedy approach, at first 5 coins are given, then 4, then 2 and then 1 coin.

So, 1 coin of 5 is given so processed denomination is 5 and remaining is 3 . So now we can not give 5 coin. Moreover, a 4 coin can not be given. So now 2 coin.

If we give 1 coin of 2 then remaining balance is 1 . So 1 coin of 1 is given.

So total coins to make total becomes : 3 ( 1 of 5, 1 of 2 and 1 of 1 ) as per the greedy approach.

But this is not the optimum solution. If we think of this, 2 coins of 4 can also give this solution.

So 2 < 3 here.

This proves that the greedy approach is not giving the best solution in this case.

Do comment if there is any query. Thank you. :)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.