Java Reference
In-Depth Information
change 31 cents in two coins, and we can change 32 cents in three coins
for a total of five coins. But the minimum remains three coins.
Again, we solve each of these subproblems recursively, which yields the
natural algorithm shown in Figure 7.23. If we run the algorithm to make small
change, it works perfectly. But like the Fibonacci calculations, this algorithm
requires too much redundant work, and it will not terminate in a reasonable
amount of time for the 63-cent case.
An alternative algorithm involves reducing the problem recursively by
specifying one of the coins. For example, for 63 cents, we can give change in
the following ways, as shown in Figure 7.24.
Our alternative
recursive change-
making algorithm is
still inefficient.
One 1-cent piece plus 62 cents recursively distributed
n
One 5-cent piece plus 58 cents recursively distributed
n
One 10-cent piece plus 53 cents recursively distributed
n
One 21-cent piece plus 42 cents recursively distributed
n
One 25-cent piece plus 38 cents recursively distributed
n
Instead of solving 62 recursive problems, as in Figure 7.22, we get by with
only 5 recursive calls, one for each different coin. Again, a naive recursive imple-
mentation is very inefficient because it recomputes answers. For example, in the
first case we are left with a problem of making 62 cents in change. In this sub-
problem, one of the recursive calls made chooses a 10-cent piece and recursively
1 // Return minimum number of coins to make change.
2 // Simple recursive algorithm that is very inefficient.
3 public static int makeChange( int [ ] coins, int change )
4 {
5 int minCoins = change;
6
7 for( int i = 0; i < coins.length; i++ )
8 if( coins[ i ] == change )
9 return 1;
10
11 // No match; solve recursively.
12 for( int j = 1; j <= change / 2; j++ )
13 {
14 int thisCoins = makeChange( coins, j )
15 + makeChange( coins, change - j );
16
17 if( thisCoins < minCoins )
18 minCoins = thisCoins;
19 }
20
21 return minCoins;
22 }
figure 7.23
A simple but
inefficient recursive
procedure for solving
the coin-changing
problem
Search WWH ::




Custom Search