Use the greedy algorithm to make change using quarters. dimes, and pennies (but no nickels) for each of the amounts given in Exercise 53. For which of these amounts does the greedy algorithm use the fewest coins of these denominations possible?

Step 1 :

In this problem we have to make change using the quarters, dimes, and pennies (but no nickels).

Step 2 :

(a) 51 cent

Ans ; 51 cent = 2 quarter + 0 dime + 1 penny=3 coin

.’. 51 cent contain only 2 quarter and 1 penny

This smallest possible number of coins.

Step 3 :

(b) 69 cent

Ans : 69 cent = 2 quarter + 1 dime + 9 penny=12 coins

.’. 69 cent contain 2 quarter,1 dime and 9 penny.

Total 12 coins.

This is not a optimal solution because 1 quarter, 4 dimes and 4 penny provides a solution with only 9 coins,