Show that if there were a coin worth 12 cents the greedy alg

Show that if there were a coin worth 12 cents, the greedy algorithm using quarters, 12-cent coins, dimes, nickels, and pennies would not always produce change using the fewest coins possible.

Solution

The greedy algorithm provides the optimum solution by making the optimal choice by seeing the optimal option available at each stage rather than taking the overall stage.

The best idea is to provide the change that will not return the least set of coins

Ex - 15 cents, using greedy algorithm, we will select 12 cent coin(1) followed by three pennies (3)

Total coins = 1 + 3 = 4

But the most optimal answer will come when we choose one dime and one nickel, in this case we get 15 cents in just 2 coins

Hence the optimal answer is 2 not 4

The another solution exists for 29 cents

In which greedy algorithm will give 1 quarter + 4 pennies (29 cents with five coins as the answer)

but the optimal answer is 2 (12 cents coin) + 1 nickel = 29 cents

Hence the optimal answer will be 3, but using greedy algorithm we will get 5 as the correct answer