Page 220 - Discrete Mathematics and Its Applications

3.1 Algorithms 199

EXAMPLE 6 Consider the problem of making n cents change with quarters, dimes, nickels, and pennies, and
using the least total number of coins. We can devise a greedy algorithm for making change for
n cents by making a locally optimal choice at each step; that is, at each step we choose the coin
of the largest denomination possible to add to the pile of change without exceeding n cents. For
example, to make change for 67 cents, we first select a quarter (leaving 42 cents). We next select
a second quarter (leaving 17 cents), followed by a dime (leaving 7 cents), followed by a nickel
(leaving 2 cents), followed by a penny (leaving 1 cent), followed by a penny. ▲

We display a greedy change-making algorithm for n cents, using any set of denominations
of coins, as Algorithm 6.

ALGORITHM 6 Greedy Change-Making Algorithm.

procedure change(c 1 ,c 2 ,...,c r : values of denominations of coins, where
c 1 >c 2 > ··· >c r ; n: a positive integer)
for i := 1 to r
d i := 0{d i counts the coins of denomination c i used}
while n ≥ c i
d i := d i + 1 {add a coin of denomination c i }
n := n − c i
{d i is the number of coins of denomination c i in the change for i = 1, 2,...,r}

We have described a greedy algorithm for making change using any finite set of coins with
denominations c 1 ,c 2 , ..., c r . In the particular case where the four denominations are quarters
dimes, nickels, and pennies, we have c 1 = 25, c 2 = 10, c 3 = 5, and c 4 = 1. For this case, we
will show that this algorithm leads to an optimal solution in the sense that it uses the fewest
coins possible. Before we embark on our proof, we show that there are sets of coins for which
the greedy algorithm (Algorithm 6) does not necessarily produce change using the fewest coins
possible. For example, if we have only quarters, dimes, and pennies (and no nickels) to use,
the greedy algorithm would make change for 30 cents using six coins—a quarter and five
pennies—whereas we could have used three coins, namely, three dimes.

LEMMA 1 If n is a positive integer, then n cents in change using quarters, dimes, nickels, and pennies
using the fewest coins possible has at most two dimes, at most one nickel, at most four
pennies, and cannot have two dimes and a nickel. The amount of change in dimes, nickels,
and pennies cannot exceed 24 cents.

Proof: We use a proof by contradiction. We will show that if we had more than the specified
number of coins of each type, we could replace them using fewer coins that have the same value.
We note that if we had three dimes we could replace them with a quarter and a nickel, if we
had two nickels we could replace them with a dime, if we had five pennies we could replace
them with a nickel, and if we had two dimes and a nickel we could replace them with a quarter.
Because we can have at most two dimes, one nickel, and four pennies, but we cannot have two
dimes and a nickel, it follows that 24 cents is the most money we can have in dimes, nickels,
and pennies when we make change using the fewest number of coins for n cents.

THEOREM 1 The greedy algorithm (Algorithm 6) produces change using the fewest coins possible.