Data Structures, Algorithms, & Applications in Java
Chapter 18, Exercise 3
$100 bills, $50 bills, $20, bills, $10 bills, $5 bills, $1 bills,
quarters, dimes, nickels, and pennies are called
currency denominations.
Dimes, nickels, and pennies are smaller denominations
than quarters and all $ denominated bills; nickels and pennies are
smaller denominations than
dimes, quarters, and all $ denominated bills; etc.
The algorithm of Example 18.4 can be used regardless of the number
of denominations available. We may combine several stages into one
to arrive at the restatement: consider the denominations in decreasing order
(i.e., in the order $100, $50, $20, ...); when a denomination is considered
give out as many of it as possible without exceeding the total amount of change
to be given out.
The greedy algorithm always generates change with the fewest number
of coins and bills. A proof of this follows.
Let H,
F,
T,
TEN,
FIVE,
ONE,
Q,
D,
N, and
P, respectively, be the number of
$100 bills, $50 bills, $20 bills, $10 bills, $5 bills, $1 bills,
quarters, dimes, nickels, and pennies in the change generated
by the greedy algorithm.
Let h,
f,
t,
ten,
five,
one,
q,
d,
n, and
p, respectively, be the corresponding numbers
for 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;
the change given in dimes, nickels, and pennies is less than 25 cents; etc.
Therefore,
F < 2,
T < 3,
TEN < 2,
FIVE < 2,
ONE < 5,
Q < 4,
D < 3,
N < 2, and
P < 5.
-
For the optimal change, we can establish
f < 2,
t < 3,
ten < 2,
five < 2,
one < 5,
q < 4,
d < 3,
n < 2, and
p < 5.
To see this, note that if
f >= 2, we can replace two $50 bills with
a $100 bill and provide the change using one less bill and the same
number of coins.
This is not possible as h+f+t+ten+five+one+q+d+n+p is the fewest number
of bills and coins with which the change can be provided.
If
t >= 3, we can replace
three $20 bills with
a $50 bill and a $10
bill and provide the change using one less bill and
the same number of coins; if
ten >= 2, we can replace two $10 bills with
a single $20 bill and provide the change using a fewer total number
of bills and coins; etc.
Hence, the total amount of change given in
lower denominations is less than the value
of the next higher denomination.
Now if H != h, then either the greedy or the optimal
solution must provide $100 or more in lower denominations.
This violates the above observations. So,
H = h. Further,
if F != f, then either the greedy or the optimal
solution must provide $50 or more in lower denominations.
This also violates the above observations. So,
F = f. We can show
T = t,
TEN = ten,
FIVE = five,
ONE = one,
Q = q,
D = d,
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 bills and coins.