1    package bookExamples.ch08ArraysAndVectors; 
2     
3    public final class Search { 
4        // Dynamic programming algorithm to solve 
5        // edge detection problem 
6        public static void Search(int[] coins, int differentCoins, 
7                                  int maxChange, int[] coinsUsed, int[] lastCoin) { 
8            coinsUsed[0] = 0; 
9            lastCoin[0] = 1; 
10    
11           for (int cents = 1; cents <= maxChange; cents++) { 
12               int minCoins = cents; 
13               int newCoin = 1; 
14    
15               for (int j = 0; j < differentCoins; j++) { 
16                   if (coins[j] > cents)   // Cannot use coin j 
17                       continue; 
18                   if (coinsUsed[cents - coins[j]] + 1 < minCoins) { 
19                       minCoins = coinsUsed[cents - coins[j]] + 1; 
20                       newCoin = coins[j]; 
21                   } 
22               } 
23    
24               coinsUsed[cents] = minCoins; 
25               lastCoin[cents] = newCoin; 
26           } 
27       } 
28    
29       // Simple test program 
30       public static void main(String[] args) { 
31           // The coins and the total amount of change 
32           int numCoins = 5; 
33           int[] coins = {1, 5, 10, 21, 25}; 
34           int change = 17; 
35    
36    
37           int[] used = new int[change + 1]; 
38           int[] last = new int[change + 1]; 
39    
40           Search(coins, numCoins, change, used, last); 
41    
42           System.out.println("Best is " + used[change] + " coins"); 
43    
44           for (int i = change; i > 0;) { 
45               System.out.print(last[i] + " "); 
46               i -= last[i]; 
47           } 
48           System.out.println(); 
49       } 
50   } 
51