數據結構與算法總結——背包問題與組和問題

• 數據結構與算法總結——背包問題與組和問題
• 1. 背包問題
• 2.背包問題的變形
• 3. 組和問題
• 總結

數據結構與算法總結——背包問題與組和問題

我覺得學習算法很重要的一點是舉一反三，題目是刷不完的（這個指的是我自己，我聽說過有刷完一千多道leetcode的大佬…），背包問題是我筆試面試過程中遇到非常多的一個類型，而且被坑了好幾次，因此我打算好好總結一下，而這個組和問題（你沒有看錯，是組和，這個是我自己取的名字，英文題目叫Combination Sum）會和背包問題由極大的相似之處，我在一次筆試的過程中將一組和問題用背包問題的解法去做而浪費的不少時間，背包問題應該是可以求出答案的，但是不如組和問題的專有解法來的干脆，因此我把這兩個問題放在一起進行一個總結。

1. 背包問題

背包問題建議看看《背包九講》，本文也主要是參考的《背包九講》中的內容，我這里主要只總結一下比較基礎的三種——01背包、完全背包、多重背包，而混合背包和分組背包我目前還沒怎么接觸過（還是做題太少…），就先不做總結了。
（1）01背包

有 $N$ 件物品和一個容量為 $V$ 的背包。放入第 $i$ 件物品耗費的費用是 $C_i^1$，得到的價值是 $W_i$。求解將哪些物品裝入背包可使價值總和最大

狀態變量定義的是 $F[i,v]$ 表示將前$i$件物品恰放入一個容量為 $v$ 的背包可以獲得的最大價值。則其狀態轉移方程便是：$$F[i,v]=\max \left\{F[i?1,v],F\left[i?1,v?C_i\right]+W_i\right\}$$其偽代碼為：$$\begin{array}{l}F[0,0..V]\leftarrow 0\\ \text{?for?}i\leftarrow 1\text{?to?}N\\ \begin{array}{rl}\text{?for?}v& \leftarrow C_i\text{?to?}V\\ & F[i,v]\leftarrow \max \left\{F[i?1,v],F\left[i?1,v?C_i\right]+W_i\right\}\end{array}\end{array}$$而對其進行空間優化之后偽代碼為：$$\begin{array}{l}F[0..V]\leftarrow 0\\ \text{?for?}i\leftarrow 1\text{?to?}N\\ \begin{array}{rl}\text{?for?}v\leftarrow & V\text{?to?}{C}_i\\ & F[v]\leftarrow \max \left\{F[v],F\left[v?C_i\right]+W_i\right\}\end{array}\end{array}$$所謂空間優化就是就是將原本的二維DP數組優化為一維DP數組，能這樣做的理由是，從未優化的偽代碼中可以看出，每次循環二維DP數組中更新的位置只和其正上方$F[i?1,v]$和左上方$F\left[i?1,v?C_i\right]$有關，因此可以用一維DP數組直接代替（這其實也叫做滾動數組），那么空間優化后的代碼如下：

int backPack(int V, vector<int> &C, vector<int> &W){int n = C.size();vector<int> F(V+1, 0);for(int i = 1; i<n; i++){for(int j = V; j>=C[i]; j--){F[j] = max(F[j],F[j-C[i]]+W[i]);}}return F[V]; }

（2）完全背包

有 $N$ 種物品和一個容量為 $V$ 的背包，每種物品都有無限件可用。放入第 $i$ 種物品的費用是 $C_i$，價值是 $W_i$。求解：將哪些物品裝入背包，可使這些物品的耗費的費用總和不超過背包容量，且價值總和最大。

這里的狀態變量的定義和01背包是一樣的，但是狀態轉移方程稍有不同，如下：$$F[i,v]=\max \left\{F\left[i?1,v?k{C}_i\right]+k{W}_i|0\le k{C}_i\le v\right\}$$其偽代碼為$$\begin{array}{l}F[0,0..V]\leftarrow 0\\ \text{?for?}i\leftarrow 1\text{?to?}N\\ \begin{array}{rl}\text{?for?}v& \leftarrow C_i\text{?to?}V\\ & \text{?for?}k\leftarrow 0\text{?to?}j/C_i\\ & F[i,v]\leftarrow \max \left\{F[i?1,v],F\left[i?1,v?k{C}_i\right]+k{W}_i\right\}\end{array}\end{array}$$完全背包由兩種優化方法，第一種是利用二進制的思想將其轉化為01背包，第二種是優化為一維數組，其時間復雜度為$O(VN)$。用得更多的是第二種方法，因為它確實很方便，第一種方法的思想主要用在多重背包問題里，那么第二種方法優化的偽代碼如下：$$\begin{array}{l}F[0..V]\leftarrow 0\\ \text{?for?}i\leftarrow 1\text{?to?}N\\ \begin{array}{rl}\text{?for?}v& \leftarrow C_i\text{?to?}V\\ & F[v]\leftarrow \max \left(F[v],F\left[v?C_i\right]+W_i\right)\end{array}\end{array}$$這里可以看出來，如果你對01背包熟悉的話，記住完全背包也就是一句話的事情，他們之間唯一不同的是第二個for循環，完全背包是從$C_i$到$V$，01背包是從$V$到$C_i$，這個規則為什么會成立呢？《背包九講》中是這么說的：

為什么這個算法就可行呢？首先想想為什么 01 背包中要按照 $v$ 遞減的次序來循環。讓 $v$ 遞減是為了保證第 $i$ 次循環中的狀態 $F[i;v]$ 是由狀態 $F[i?1;v?C_i]$遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第 $i$ 件物品”這件策略時，依據的是一個絕無已經選入第 $i$ 件物品的子結果 $F[i?1;v?C_i]$。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第 $i$ 種物品”這種策略時，卻正需要一個可能已選入第 i 種物品的子結果 $F[i;v?C_i]$，所以就可以并且必須采用 $v$ 遞增的順序循環。這就是這個簡單的程序為何成立的道理。

這里給出按照第二種優化后的代碼（其實真的就是把上面的代碼趴下來改一句話就行了）

int backPack(int V, vector<int> &C, vector<int> &W){int n = C.size();vector<int> F(V+1, 0);for(int i = 1; i<n; i++){for(int j = C[i]; j<=V; j--){F[j] = max(F[j],F[j-C[i]]+W[i]);}}return F[V]; }

（3）多重背包

有 $N$ 種物品和一個容量為 $V$ 的背包。第 $i$ 種物品最多有 $M_i$ 件可用，每件耗費的空間是 $C_i$，價值是 $W_i$。求解將哪些物品裝入背包可使這些物品的耗費的空間總和不超過背包容量，且價值總和最大。

同樣，多重背包的狀態變量定義和前兩者是相同的，不同的還是狀態轉移方程，如下：$$F[i,v]=\max \left\{F\left[i?1,v?k?C_i\right]+k?W_i|0\le k\le M_i\right\}$$多重背包通常采用的優化方式是通過二進制思想轉化為01背包進行求解，所謂二進制思想按照我的個人理解就是，通過給數量為$M_i$個的物體 $i$ 帶上二進制標簽 $2^k$ 之后相當于變成了多個數量為 1 的物體，然后通過對這些數量為 1 的物體采用取或者不取的方式最后組合成取具體數量的物體 $i$ 。這里直接給出一段多重背包的代碼，具體怎么進行二進制的可以通過代碼進行理解

int main() {int n, w;cin>>n>>w;vector<int> weights;//物體重量vector<int> values;//物體價值vector<int> nums;//物體數量for(int i = 0; i<n; i++){int weight, value, num;cin>>weight>>value>>num;int temp = 1;while(num)//在輸入的時候進行二進制化{if(num>=temp){weights.push_back(temp * weight);values.push_back(temp * value);num -= temp;}else{weights.push_back(num * weight);values.push_back(num * weight);num = 0;}temp *= 2;}}//下面就是直接調用01背包的程序就可以了vector<int> dp(w+1, 0);for(int i = 0; i<weights.size(); i++){for(int j = w; j>=weights[i]; j--){dp[j] = max(dp[j], dp[j-weights[i]]+values[i]);}}cout<<dp[w]; }

上面的程序是在輸入的時候就直接根據物體的數量對物體的價值和重量進行二進制化，temp就是用來進行二進制化的變量，在循環中temp分別是$1,2,2^2\dots 2^{k?1},M_i?2^k+1$，通過將物體的價值和重量乘以這些系數實現二進制化，二進制化物體直接采用01背包的策略就可以直接求得多重背包最終的結果。

2.背包問題的變形

好了，真正的重點來了，通過背包問題的變形我們將引出來組和問題，注意到，上面的背包問題都是最典型形式，問的都是給定一個背包容量$V$，怎么取放物體使得裝下的價值$W$最大 ，這類問題的狀態變量的意義是價值，以01背包為例，其狀態轉移方程為$$F[i,v]=\max \left\{F[i?1,v],F\left[i?1,v?C_i\right]+W_i\right\}$$那么背包問題有一種很典型的變形形式是給定一個背包容量$V$，怎樣取放物體可以放滿背包，一共有幾種取放方式，對于這個問題，我們就需要將狀態變量的意義定義為滿足方面背包條件的情況種類，以01背包為例，其狀態轉移方程就變為：$$F[i,v]=F[i?1,v]+F\left[i?1,v?C_i\right]$$對應的代碼也給出來

int combinationSum(int V, vector<int> &C){int n = C.size();vector<int> F(V+1, 0);V[0] = 1;for(int i = 1; i<n; i++){for(int j = V; j>=C[i]; j--){F[j] = F[j]+F[j-C[i]];}}return F[V]; }

注意這里，除了狀態轉移方程有點不太一樣之外，還有就是初始話的時候需要將V[0]初始話為1，這里注意一下就好了，這類問題又稱找零錢問題，leetcode中還有一個找零錢問題的變形（332題），如下：

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

這個題目看上去像是完全背包問題，但是題目所求的既不是最大價值，也不是方案數，而是最少的硬幣個數，這個怎么做呢？方法也是使用動態規劃，但是狀態轉移方程的思路和上述討論的方式不太相同，具體如下，我們維護一個一維動態數組 dp，其中 dp[i] 表示錢數為i時的最小硬幣數的找零，注意由于數組是從0開始的，所以要多申請一位，數組大小為 amount+1，這樣最終結果就可以保存在 dp[amount] 中了。初始化 dp[0] = 0，因為目標值若為0時，就不需要硬幣了。其他值可以初始化是 amount+1，為啥呢？因為最小的硬幣是1，所以 amount 最多需要 amount 個硬幣，amount+1 也就相當于當前的最大值了，注意這里不能用整型最大值來初始化，因為在后面的狀態轉移方程有加1的操作，有可能會溢出，除非你先減個1，這樣還不如直接用 amount+1 舒服呢。好，接下來就是要找狀態轉移方程了，沒思路？不要緊！回歸例子1，假設我取了一個值為5的硬幣，那么由于目標值是 11，所以是不是假如我們知道 dp[6]，那么就知道了組成 11 的 dp 值了？所以更新 dp[i] 的方法就是遍歷每個硬幣，如果遍歷到的硬幣值小于i值（比如不能用值為5的硬幣去更新 dp[3]）時，用 dp[i - coins[j]] + 1 來更新 dp[i]，所以狀態轉移方程為（分析來源[LeetCode] 322. Coin Change 硬幣找零）：$$dp[i]=min(dp[i],dp[i?coins[j]]+1)$$代碼如下：

int coinChange(vector<int>& coins, int amount) {if(coins.empty())return 0;vector<int> dp(amount+1,amount+1);dp[0] = 0;for(int i = 1; i<=amount; i++){for(int j = 0; j<coins.size(); j++){if(coins[j]<=i){dp[i] = min(dp[i], dp[i-coins[j]]+1);}}}return dp[amount] == amount+1 ? -1 : dp[amount]; }

這里需要讀者細細去理解這幾種變形中的不同，然后我們繼續變形，現在僅僅是要求輸出有多少種情況，如果題目要求將所有的情況都打印出來呢？用背包能做嗎？答案是可以的，但是比較麻煩，一種更加簡單的思路是采用回溯加剪枝，也就是圖論的方式去解決，也就是接下來要討論的組和問題。

3. 組和問題

組和問題在leetcode中一共由四道，是一個系列，分別是
39. 組合總和
40. 組合總和 II
216. 組合總和 III
377. 組合總和 Ⅳ
其實這個系列并不難，簡單分析下：
（1）組和問題

給定一個無重復元素的數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。 candidates 中的數字可以無限制重復被選取。

這個其實就是相當于背包問題中的完全背包問題，完成組和問題需要實現一個深度搜索的函數，具體代碼如下：

void dfs(vector<int>& candidates, int target, int start, vector<int>& out, vector<vector<int>>& res) {if(target<0)return;if(target == 0){res.push_back(out);return;}for(int i = start; i<candidates.size(); i++){out.push_back(candidates[i]);dfs(candidates, target-candidates[i], i, out, res);out.pop_back();} }vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> res;vector<int> out;dfs(candidates, target, 0, out, res); return res; }

（2）組和問題II

給定一個數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。candidates 中的每個數字在每個組合中只能使用一次。

這個相當于是01背包問題，和上面稍有不同的處理方式是，這里因為每個數字只能使用一次，因此需要先對數組進行一次排序，然后遞歸取數的時候控制不要重復取就好了，代碼如下：

void dfs(vector<int>& candidates, int target, int start, vector<int>& out, vector<vector<int>>& res) {if(target<0)return;if(target == 0){res.push_back(out);return;}for(int i = start; i<candidates.size(); i++){if(i>start && candidates[i] == candidates[i-1]) continue;//判斷相鄰兩個數據是否相同，避免重復out.push_back(candidates[i]);dfs(candidates, target-candidates[i], i+1, out, res);//將i改成i+1，避免重復out.pop_back();} }vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> res;vector<int> out;sort(candidates.begin(), candidates.end());dfs(candidates, target, 0, out, res);return res; }

（3）組和問題III

找出所有相加之和為 n 的 k 個數的組合。組合中只允許含有 1 - 9 的正整數，并且每種組合中不存在重復的數字。

還是很類似的，這里只是規定了取的個數，有點類似與多重背包，但不完全是，代碼如下：

void dfs(int k, int n, int start, vector<int>& out, vector<vector<int>>& res) {if(n<0)return;if(n == 0 && out.size() == k)//這里限制了取的數量{res.push_back(out);return;}for(int i = start; i<=9; i++){out.push_back(i);dfs(k, n-i, i+1, out, res);//i+1保證了不會重復取out.pop_back();} }vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> res;vector<int> out;dfs(k, n, 1, out, res);return res; }

（4）組和問題IV

給定一個由正整數組成且不存在重復數字的數組，找出和為給定目標正整數的組合的個數。

這是何方神圣？這不就是01背包嗎！是的，但是leetcode上這道題和01背包有些不同的是，組合的順序不同屬于不同的組合，因此其和01背包的解題思路會稍有差別，先看代碼

int combinationSum4(vector<int>& nums, int target) {int n = nums.size();vector<int> dp(target+1);dp[0] = 1;for(int i = 1; i<=target; i++){for(int j = 0; j<n; j++){if(i>=nums[j])dp[i] = dp[i] + dp[i-nums[j]];}}return dp[target]; }

觀察發現和01背包不同的是，如果要求組合的順序不同屬于不同的組合，就內外循環的順序換一下就好了，這個解法的思路和爬梯子的思路就更加相似的，比如說對于 [1,2,3] 4，這個例子，當我們在計算 dp[3] 的時候，3可以拆分為 1+x，而x即為 dp[2]，3也可以拆分為 2+x，此時x為 dp[1]，3同樣可以拆為 3+x，此時x為 dp[0]，我們把所有的情況加起來就是組成3的所有情況了。

總結

通過上面的分析可以看出來，如果是求方案數的話通常是用動態規劃的方法，如果是要求輸出方案的話通常是用回溯加剪枝的方法，從本質上說，這兩者是等價的，最終都是搜索了一顆隱式樹，回溯加剪枝是深度優先搜索的過程，而動態規劃更像是層序遍歷的過程，真正體會這兩者之間的關系我還需要刷更多的題。

總結

以上是生活随笔為你收集整理的数据结构与算法总结——背包问题与组和问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。