首页 > 代码库 > 一个货币组合的问题
一个货币组合的问题
今年五月份的时候，宿舍的人找实习，笔试碰到一道货币组合的问题，是这样子的：
现在我们有1元、2元、5元、10元、20元和50元，每种面值都有若干张。请问，如果要用这些货币组成100元的话，有多少种方法？
他们笔试回来，就讲了这个问题。当时本菜就写了个暴力的方法（反正计算机有这么大的算力……）
1 #include <cstdio> 2 #include <cstdlib> 3 4 int 5 main(int argc, char** argv) 6 { 7 int count = 0; 8 int sum = 0; 9 10 for (int fifty = 0; fifty <=2 ; fifty++) {11 for (int twenty = 0; twenty <= 5; twenty++) {12 for (int ten =0; ten <= 10; ten++) {13 for (int five = 0; five <= 20; five++) {14 for (int two = 0; two <= 50; two++) {15 for (int one = 0; one <= 100; one++) {16 sum = 50*fifty + 20*twenty + 10*ten + 5*five + 2*two + 1*one;17 if (sum != 100) {18 continue;19 }20 count++;21 }22 }23 }24 }25 }26 }27 28 printf("total combination: %d.\n", count);29 30 system("pause");31 return 0;32 }
这种方法容易想，但是不容易扩展。如果货币的种类变更，比如现在规定不允许使用2元，然后多了100元的货币可供选择。那么代码要改的地方就多了。
同时，程序的运行速度也不快（暂不考虑）。
最近学了点动态规划的知识，尤其是0-1背包问题。感觉跟这个货币组合的问题有点类似，想法是这样的：
定义函数f(i, j)：要组合的货币目标为i，可供选择的货币从第0到第j种（可以把j看成大小为j的数组，在本题中v[0]=1, v[1]=2, v[2] =5……），f就是在i，j的条件下，货币组合的数目。(i > 0, j >= 0)
所以我们可以知道，
- 当i = 1时，组合目标为1元，只能用1张1元来组合。那么f(i, j) = 1。
- 当j = 0时，那么无论组合目标为多少，只有1元钱能够用来组合。那么f(i, j) = 1。
- 当i < v[j]时，比i大的v[j]是不能用来组合的，所以f(i, j) = f(i, j-1)。
- 当i = v[j]时，有两种情况，一是用1张的v[j]来组合；二是没有用到v[j]，组合方法有f(i, j-1)种，所以f(i, j) = 1 + f(i, j-1)。
- 当i > v[j]时，这是最普遍的情形。有两种情况，一是没用到v[j]，是f(i, j-1)；二是用到了一张v[j]，但是仍然可以再用v[j]，所以是f(i-v[j], j)。则两者相加，一共是f(i, j-1)+f(i-v[j], j)。
或者可以这样思考第五步的第二种情况：只用了一张v[j]，是f(i-v[j], j-1)，用到两张v[j]，是f(i-2*v[j], j-1)，用到三张v[j]，是f(i-3*v[j], j-1)......所以f(i, j) = f(i, j-1) + f(i-v[j], j-1) + f(i-2*v[j], j-1) + f(i-3*v[j], j-1)+......
而f(i-v[j], j) = f(i-v[j], j-1) + f(i-2*v[j], j-1) + f(i-3*v[j], j-1) + ......代入上一段的f(i, j)，可以得到f(i, j) = f(i, j-1) + f(i-v[j], j)，同第五步。
根据1~5的分析，我们可以写出递归的函数：
int v[6] = {1, 2, 5, 10, 20, 50}; // 零钱面额// 递归版本// idxChange为零钱的序号，sum为货币组合的目标金额int MoneyCombination(int sum, int idxChange){ if (sum == 1 || idxChange == 0) { return 1; } if (sum < v[idxChange]) { return MoneyCombination(sum, idxChange-1); } if (sum == v[idxChange]) { return 1 + MoneyCombination(sum, idxChange-1); } return MoneyCombination(sum, idxChange-1) + MoneyCombination(sum-v[idxChange], idxChange);}
同理我们可以写出非递归的函数：
1 // 非递归版本 2 // table也可以为[100][6]，此处设为[101][6]，便于理解 3 int v[6] = {1, 2, 5, 10, 20, 50}; 4 int table[101][6] = {0}; 5 int MoneyCombination(void) 6 { 7 // i为货币组合的目标金额，j为零钱的序号 8 int i, j; 9 i = 0; 10 j = 0;11 // 初始化第二步的情况。我们忽略第一步的情况，因为它被包含在第二步和第三步的处理当中。 12 for (i = 1; i < 101; i++) {13 table[i][0] = 1;14 }15 for (i = 1; i < 101; i++) {16 for (j = 1; j < 6; j++) {17 if (i < v[j]) {18 table[i][j] = table[i][j-1];19 }20 if (i == v[j]) {21 table[i][j] = 1 + table[i][j-1];22 }23 if (i > v[j]) {24 table[i][j] = table[i][j-1] + table[i-v[j]][j];25 }26 }27 }28 return table[100][5];29 }
也同理，我们可以写出打印零钱组合的函数（此函数亦可以计算零钱组合）：
1 // 打印零钱组合，原理还是动态规划的原理 2 int v[6] = {1, 2, 5, 10, 20, 50}; 3 string result; 4 string str[6] = {"1", "2", "5", "10", "20", "50"}; 5 int count = 0; 6 7 void print(int i, int j, string result) 8 { 9 if (i == 0 && j == 0) {10 printf("%s\n", result.c_str());11 count++;12 }13 else if (i > 0 && j == 0) {14 print(i-v[j], j, result + str[j]+ " ");15 }16 17 else if (i < v[j]) {18 print(i, j-1, result);19 }20 else if (i > 0 && j > 0) {21 print(i-v[j], j, result + str[j] + " ");22 print(i, j-1, result);23 }24 }
动态规划只学了一点点，正好用在了解答这道题目上。算法是很有趣的东西，值得我们去琢磨。
参考：
整数拆分问题
用1元，2元，5元，10元，20元和50元的纸币组成100元，共有多少种情况？
一个货币组合的问题