Use the greedy algorithm to make change using quarters, dimes, and pennies (but no nickels) for each of the amounts given in Exercise 52. For which of these amounts does the greedy algorithm use the fewest coins of these denominations possible?
Solution: Step 1 :In this problem we have to make change using the quarters, dimes, and pennies (but no nickels).Step 2 : (a) 87 centAns ; 87 cent = 3 quarter + 1 dime + 2 penny=6 coin .’. 87 cent contain only 3 quarter,1 dime and 2 penny.Total 6 coins. This smallest possible number of coins.Step 3 :(b) 49 cent Ans : 49 cent = 1 quarter + 2 dime + 4 penny=7 coins.’. 49 cent contain 1 quarter,2 dime and 4 penny.This is a optimal solution this contain only 7 coins.This smallest possible number of coins.