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.

Question

Karlee Marsh

Mathematics

25 November, 11:52

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)

Know the Answer?

Ishaan Kidd · Answer 1

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.