Question

Suppose we want to make change for n cents, using 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. Either give a counter example, to prove that this algorithm can output a non-optimal solution or prove that this algorithm always outputs an optimal solution.

Answer 1

This algorithm does not always give the optimal solution.

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.