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 coin possible

Solution

We are allowed to use each coin any number of times, so we can use as many quarters as we can, then the lower dimenision dimes then nickels and then pennies to compensate for the exact amount

Let us suppose we want to need 15 cents as the amount

then mimimum tries will be 1 dime(10 cents) + 1 nickel (5 cents) = 15 cents (2 coins)

but the greedy algorithm will give us the answer that use 1 12-cent coin and three pennies

12-cent coin + 3*(1-cent penny) = 15 cents (4 coins)

Hence the answer in this case will not be correct using the greedy algorithm approach

The 12-cent also provide alternative examples for his usefulness example take 29 cents

previous case we have taken 1 quarter + 4 pennies ( 5 coints) which can be done efficiently in 2-12 cents + 1 nickel coin

Hence the 12-cent coin will provide better results in some cases as well but with the example of 15 cents case we can show that it will not be efficient using greedy algorithm described in 1st line