Question

Use the greedy algorithm to make change using quarters, dimes, nickels, and pennies for

a) 87 cents. b) 49 cents.

c) 99 cents. d) 33 cents.

Short answer

Subpart (a):

Hence, 87 cents can be changed with 3 quarters, 1 dime, and 2 pennies.

Subpart (b):

Hence, 49 cents can be changed with 1 quarters, 2 dime, and 4 pennies.

Subpart (c):

Hence, 99 cents can be changed with 3 quarters, 2 dime, and 4 pennies.

Subpart (d):

Hence, 33 cents can be changed with 1 quarters, 1 nickel, and 3 pennies.

Step-by-step solution

Subpart (a):

Step 1:

So, the conversion between U.S. coins are:

1 penny = 1 cents

1 nickle = 5 cents

1 dime = 10 cents

1 quarter = 25 cents

Step 2:

So, by greedy change algorithm 87cents can have following combinations of quarters, dimes, nickels, and pennies:

3 quarters = 75 cents

1 dime = 10 cents]

2 pennis = 2 cents

Therefore, 87 cents can be changed with 3 quarters, 1 dime, and 2 pennies.

Subpart (b):

Step 1:

So, the conversion between U.S. coins are:

1 penny = 1 cents

1 nickel = 5 cents

1 dime = 10 cents

1 quarter = 25 cents

Step 2:

So, by greedy change algorithm 49 cents can have following combinations of quarters, dimes, nickels, and pennies:

$$\begin{gathered} 1quarter=25cents \\ 2dime=20cents \\ 4pennis=4cents \end{gathered}$$
Therefore, 49 cents can be changed with 1 quarters, 2 dime, and 4 pennies.

Subpart (c):

Step 1:

So, the conversion between U.S. coins are:

$$\begin{gathered} 1penny=1cents \\ 1nickel=5cents \\ 1dime=10cents \\ 1quarter=25cents \end{gathered}$$

Step 2:

So, by greedy change algorithm 99 cents can have following combinations of quarters, dimes, nickels, and pennies:

$$\begin{gathered} 3quarters=75cents \\ 2dimes=20cents \\ 4pennies=4cents \end{gathered}$$

Therefore, 99cents can be changed with 3 quarters, 2 dime, and 4 pennies.

Subpart (d):

Step 1:

So, the conversion between U.S. coins are:

$$\begin{gathered} 1penny=1cents \\ 1nickel=5cents \\ 1dime=10cents \\ 1quarter=25cents \end{gathered}$$

Step 2:

So, by greedy change algorithm 33 cents can have following combinations of quarters, dimes, nickels, and pennies:

$$\begin{gathered} 1quarters=25cents \\ 1nickel=5cents \\ 3pennis=3cents \end{gathered}$$

Therefore, 33 cents can be changed with 1 quarters, 1 nickel, and 3 pennies.