Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 1
Quarters, dimes, nickels, and pennies are called
currency denominations.
Dimes, nickels, and pennies are smaller denominations
than quarters; nickels and pennies are smaller denominations than
dimes; etc.
Let Q,
D,
N, and
P, respectively, be the number of
quarters, dimes, nickels, and pennies in the change generated
by the greedy algorithm.
Let q,
d,
n, and
p, respectively, be the number of
quarters, dimes, nickels, and pennies in the change generated
by an optimal algorithm.
We make the following observations:
-
From the way the greedy algorithm works, it follows that the
total amount of change given in lower denominations is less than the value
of the next higher denomination. That is, the change given in pennies is less
than
5 cents; the change given in pennies and nickels is less than 10 cents;
and the change given in dimes, nickels, and pennies is less than 25 cents.
Therefore,
D < 3,
N < 2, and
P < 5.
-
For the optimal change, we can establish
d < 3,
n < 2, and
p < 5.
To see this, note that if
d >= 3, we can replace three dimes by
a quarter and a nickel and provide the change using one less coin.
This is not possible as q+d+n+p is the fewest number
of coins with which the change can be provided.
If
n >= 2, we can replace two nickels by
a dime and provide the change using one less coin; and if
p >= 5, we can replace five pennies by
a nickel and provide the change using four fewer coins.
Hence, the total amount of change given in
lower denominations is less than the value
of the next higher denomination.
Now if Q != q, then either the greedy or the optimal
solution must provide 25 cents or more in lower denominations.
This violates the above observations. So,
Q = q. Further,
if D != d, then either the greedy or the optimal
solution must provide 10 cents or more in lower denominations.
This also violates the above observations. So,
D = d. We can show
N = n
and
P = p
in a similar way.
Therefore, the greedy and optimal solutions are the same.
Hence the greedy algorithm always provides change using the fewest number
of coins.