Ask Question
12 October, 14:59

Suppose we need to make change for n cents, and we want to use the least number of coins of denominations 1, 10, and 25 cents. Consider the following greedy strategy: suppose the amount left to change is m. Take the largest coin that is no more than m, subtract this coin's value from m, and repeat. Prove that this algorithm is optimal, or give a counterexample if it is not.

+5
Answers (1)
  1. 12 October, 15:41
    0
    Explained

    Step-by-step explanation:

    This algorithm does not always give the optimal solution. There is an alternate method as well.

    Consider we have to make change for 30 cents, using the least number of coins of denominations 1,10 and 25 cents. According to the given strategy, we first take a 25 cents coin and subtract it from 30 cents. Now, we have to make 5 cents which we can make only from 5 one-cent coins. So, the total number of coins required is 6 according to the given greedy strategy.

    But we can simply use 3 ten-cent coins to make change of 30 cents. So, this example proves that the given strategy is not an optimal one.
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “Suppose we need to make change for n cents, and we want to use the least number of coins of denominations 1, 10, and 25 cents. Consider the ...” in 📙 Mathematics if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers