## 題目描述 輸入兩個整數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}] 即可。