动态规划2.2 硬币找零

问题：

　　假设我们有几种不同币值的硬币，v1、v2、......、vn，如果我们要支付w元，求最少需要多少个硬币？

　　假设有三种不同的硬币，1元、3元、5元。

代码：

 1 #include <iostream>
 2 #include <string.h>
 3 
 4 int main()
 5 {
 6     int value[3] = {1, 3, 5};   // 三种面值的硬币
 7      
 8     // 假设要支付w元。则最多需要w个硬币，因为最小面值为1元。
 9     #define w 9
10     
11     int states[w][w+1] = {0};  // 用于记录到达某个节点时所使用的硬币的数量
12     for(int i = 0; i < w; i++) // 初始化为一个较大的值
13         for(int j = 0; j < w + 1; j++)
14             states[i][j] = 0xffff;
15     
16     int matrix[w][w+1] = {0};  // 用于记录总的钱数
17     
18     matrix[0][1] = 1;
19     matrix[0][3] = 1;
20     matrix[0][5] = 1;
21     
22     states[0][1] = 1;
23     states[0][3] = 1;
24     states[0][5] = 1;
25     int num = 0;
26     for(int i = 1; i < w; i++)
27     {
28         for(int j = 0; j < w + 1; j++)
29         {
30             for(int k = 0; k < sizeof(value) / sizeof(int); k++)
31             {
32                 if(matrix[i-1][j] == 1)
33                 {
34                     if(matrix[i-1][j] + value[k] < w + 1)
35                     {
36                         if(states[i-1][j] == 0xffff)
37                         {
38                             states[i][j + value[k]] = 1;
39                             matrix[i][j + value[k]] = 1; 
40                             if(j + value[k] == w)
41                             {
42                                 std::cout << "j :" << j << ", k :" << k << std::endl;
43                                 num = states[i][w];
44                                 goto end;
45                             }
46                         }
47                         else if(states[i-1][j] + 1 < states[i][j+value[k]])
48                         {
49                             states[i][j + value[k]] = states[i-1][j] + 1;
50                             matrix[i][j + value[k]] = 1; 
51                             if(j + value[k] == w)
52                             {
53                                 std::cout << "j :" << j << "k :" << k << std::endl;
54                                 num = states[i][w];
55                                 goto end;
56                             }
57                         }
58                     }
59                 }    
60             }
61         }
62     }
63     end:
64     
65     std::cout << "num : " << num << std::endl;
66     
67     return 0;
68 }

运行结果：

下面的实现比较简洁：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <vector>
 4 
 5 int min3(int a, int b, int c)
 6 {
 7     return std::min( std::min(a, b), c );
 8 }
 9 
10 int min_coin(int money)
11 {
12     //{0, 1, 2, 1, 2, 1};    币值为0 1 2 3 4 5时对应的找零硬币个数
13     
14     std::vector<int> s(money + 1, 0);
15     s[0] = 0;
16     s[1] = 1;
17     s[2] = 2;
18     s[3] = 1;
19     s[4] = 2;
20     s[5] = 1;
21     
22     for(int i = 6; i < money + 1; i++)
23     {
24         s[i] = min3(s[i - 1], s[i - 3], s[i - 5]) + 1;
25     }
26     
27     return s[money];
28 }
29 
30 int main()
31 {
32     int coins = min_coin(9); // 9元找零
33     
34     std::cout << "coins : " << coins << std::endl;
35     
36     return 0;
37 }

运行结果：