## 题目描述 输入两个整数n和sum,从数列1,2,3.......n 中随意取几个数,使其和等于sum,要求将其中所有的可能组合列出来。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.03.md#分析与解法)分析与解法 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.03.md#解法一)解法一 注意到取n,和不取n个区别即可,考虑是否取第n个数的策略,可以转化为一个只和前n-1个数相关的问题。 * 如果取第n个数,那么问题就转化为“取前n-1个数使得它们的和为sum-n”,对应的代码语句就是sumOfkNumber(sum - n, n - 1); * 如果不取第n个数,那么问题就转化为“取前n-1个数使得他们的和为sum”,对应的代码语句为sumOfkNumber(sum, n - 1)。 参考代码如下: ~~~ list<int>list1; void SumOfkNumber(int sum, int n) { // 递归出口 if (n <= 0 || sum <= 0) return; // 输出找到的结果 if (sum == n) { // 反转list list1.reverse(); for (list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++) cout << *iter << " + "; cout << n << endl; list1.reverse()//此处还需反转回来 } list1.push_front(n); //典型的01背包问题 SumOfkNumber(sum - n, n - 1); //“放”n,前n-1个数“填满”sum-n list1.pop_front(); SumOfkNumber(sum, n - 1); //不“放”n,n-1个数“填满”sum } ~~~ ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.03.md#解法二)解法二 这个问题属于子集和问题(也是背包问题)。本程序采用回溯法+剪枝,其中X数组是解向量,t=∑(1,..,k-1)Wi*Xi, r=∑(k,..,n)Wi,且 * 若t+Wk+W(k+1)<=M,则Xk=true,递归左儿子(X1,X2,..,X(k-1),1);否则剪枝; * 若t+r-Wk>=M && t+W(k+1)<=M,则置Xk=0,递归右儿子(X1,X2,..,X(k-1),0);否则剪枝; 本题中W数组就是(1,2,..,n),所以直接用k代替WK值。 代码编写如下: ~~~ //输入t, r, 尝试Wk void SumOfkNumber(int t, int k, int r, int& M, bool& flag, bool* X) { X[k] = true; // 选第k个数 if (t + k == M) // 若找到一个和为M,则设置解向量的标志位,输出解 { flag = true; for (int i = 1; i <= k; ++i) { if (X[i] == 1) { printf("%d ", i); } } printf("\n"); } else { // 若第k+1个数满足条件,则递归左子树 if (t + k + (k + 1) <= M) { SumOfkNumber(t + k, k + 1, r - k, M, flag, X); } // 若不选第k个数,选第k+1个数满足条件,则递归右子树 if ((t + r - k >= M) && (t + (k + 1) <= M)) { X[k] = false; SumOfkNumber(t, k + 1, r - k, M, flag, X); } } } void search(int& N, int& M) { // 初始化解空间 bool* X = (bool*)malloc(sizeof(bool)* (N + 1)); memset(X, false, sizeof(bool)* (N + 1)); int sum = (N + 1) * N * 0.5f; if (1 > M || sum < M) // 预先排除无解情况 { printf("not found\n"); return; } bool f = false; SumOfkNumber(0, 1, sum, M, f, X); if (!f) { printf("not found\n"); } free(X); } ~~~ ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.03.md#0-1背包问题)0-1背包问题 0-1背包问题是最基础的背包问题,其具体描述为:有N件物品和一个容量为V的背包。放入第i件物品耗费的费用是Ci,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。 简单分析下:这是最基础的背包问题,特点是每种物品仅有一件,可以选择放或不放。用子问题定义状态:即F[i, v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是: * F[i, v] = max{F[i-1, v], F[i-1, v-Ci ] + Wi} 根据前面的分析,我们不难理解这个方程的意义:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只和前 i-1 件物品相关的问题。即: * 如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为 F[i-1, v ]; * 如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-Ci的背包中”,此时能获得的最大价值就是F[i-1, v-Ci]再加上通过放入第i件物品获得的价值Wi。 伪代码如下: ~~~ F[0,0...V] ← 0 for i ← 1 to N for v ← Ci to V F[i, v] ← max{F[i-1, v], F[i-1, v-Ci] + Wi } ~~~ 这段代码的时间和空间复杂度均为 O(VN),其中时间复杂度应该已经不能再优化了,但空间复杂度却可以优化到O(V)。感兴趣的读者可以继续思考或者参考网上一个不错的文档《背包问题九讲》。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.03.md#举一反三)举一反三 1、《挑战程序设计竞赛》的开篇有个类似的抽签问题,挺有意思,题目如下: 将写有数字的n个纸片放入一个纸箱子中,然后你和你的朋友从纸箱子中抽取4张纸片,每次记下纸片上的数字后放回子箱子中,如果这4个数字的和是m,代表你赢,否则就是你的朋友赢。 请编写一个程序,当纸片上所写的数字是k1,k2,k3,k4,..,kn时,是否存在抽取4次和为m的方案,如果存在,输出YES;否则,输出NO。 限制条件: * 1 <= n <= 50 * 1 <= m <= 10^8 * 1 <= ki <= 10^8 分析:最容易想到的方案是用4个for循环直接穷举所有方案,时间复杂度为O(N^4),主体代码如下: ~~~ //通过4重for循环枚举所有方案 for (int a = 0; a < n, a++) { for (int b = 0; b < n; b++) { for (int c = 0; c < n; c++) { for (int d = 0; d < n; d++) { if (k[a] + k[b] + k[c] + k[d] == m) { f = true; } } } } } ~~~ 但如果当n远大于50时,则程序会显得非常吃力,如此,我们需要找到更好的办法。 提供两个思路: ①最内侧关于d的循环所做的事情:检查是否有d满足ka+ kb +kc + kd = m,移动下式子,等价于:检查是否有d使得kd = m - ka - kb - kc,也就是说,只要检查k中所有元素,判断是否有等于m-ka-kb-ka 的元素即可。设m-ka-kb-ka = x,接下来,就是要看x是否存在于数组k中,此时,可以先把数组k排序,然后利用二分查找在数组k中找x; ②进一步,内侧的两个循环所做的事情:检查是否有c和d满足kc + kd = m - ka -kb。同样,可以预先枚举出kc+kd所得的n^2数字并排好序,便可以利用二分搜索继续求解。 2、给定整数a1、a2、a3、...、an,判断是否可以从中选出若干个数,使得它们的和等于k(k任意给定,且满足-10^8 <= k <= 10^8)。 分析:此题相对于本节“寻找满足条件的多个数”如出一辙,不同的是此题只要求判断,不要求把所有可能的组合给输出来。因为此题需要考虑到加上a[i]和不加上a[i]的情况,故可以采用深度优先搜索的办法,递归解决。 3、有n个数,输出期中所有和为s的k个数的组合。 分析:此题有两个坑,一是这里的n个数是任意给定的,不一定是:1,2,3...n,所以可能有重复的数(如果有重复的数怎么处理?);二是不要求你输出所有和为s的全部组合,而只要求输出和为s的k个数的组合。 举个例子,假定n=6,这6个数为:1 2 1 3 0 1,如果要求输出和为3的全部组合的话, * 1 2 * 1 2 0 * 0 3 * 1 1 1 * 1 1 1 0 而题目加了个限制条件,若令k=2,则只要求输出:[{1,2}, {0,3}] 即可。