Java Reference
In-Depth Information
example of so-called greedy algorithms. In a greedy algorithm , during each
phase, a decision is made that appears to be optimal, without regard for future
consequences. This “take what you can get now” strategy is the source of the
name for this class of algorithms. When a problem can be solved with a
greedy algorithm, we are usually quite happy: Greedy algorithms often match
our intuition and make for relatively painless coding. Unfortunately, greedy
algorithms do not always work. If the U.S. currency included a 21-cent piece,
the greedy algorithm would still give a solution that uses six coins, but the
optimal solution uses three coins (all 21-cent pieces).
The question then becomes one of how to solve the problem for an arbi-
trary coin set. We assume that there is always a 1-cent coin so that the solution
always exists. A simple strategy to make K cents in change uses recursion as
follows.
1.
If we can make change using exactly one coin, that is the minimum.
2.
Otherwise, for each possible value i we can compute the minimum
number of coins needed to make i cents in change and K - i cents in
change independently. We then choose the i that minimizes this sum.
For example, let us see how we can make 63 cents in change. Clearly,
one coin will not suffice. We can compute the number of coins required
to make 1 cent of change and 62 cents of change independently (these are
1 and 4, respectively). We obtain these results recursively, so they must
be taken as optimal (it happens that the 62 cents is given as two 21-cent
pieces and two 10-cent pieces). Thus we have a method that uses five
coins. If we split the problem into 2 cents and 61 cents, the recursive
solutions yield 2 and 4, respectively, for a total of six coins. We continue
trying all the possibilities, some of which are shown in Figure 7.22.
Eventually, we see a split into 21 cents and 42 cents, which is changeable
in one and two coins, respectively, thus allowing change to be made in
three coins. The last split we need to try is 31 cents and 32 cents. We can
A simple recursive
algorithm for
change-making is
easily written but
inefficient.
figure 7.22
Some of the
subproblems solved
recursively in
Figure 7.23
1
21
1
21
62
42
21
21
10
10
21
21
2
31
1
1
21
10
61
32
25
25
10
1
21
10
1
Search WWH ::




Custom Search