九种 0-1 背包问题详解
目錄
動態規劃概念
問題1：0-1背包問題
問題2：完全背包問題
問題3：多重背包問題
問題4：混合背包問題
問題5：二維背包問題
問題6：分組背包問題
問題7：有依賴的背包問題?(困難)
問題8：背包問題求方案數
問題9：背包問題求具體方案
前言
0-1 背包是一個經典的問題，之前也整理過一篇關于 0-1 背包的博客，當時只是整理了 0-1 背包問題的?4 種解決方法。最近在復習算法，發現有很多 0-1 背包問題的衍生問題。0-1 背包問題的限制條件既可以是重量，也可以是容量，或者兩者同時限制?，F在將這?9 種 0-1?背包問題與解決方法整理出來。這 9 種 0-1?背包問題實質上都是在問題 1 的基礎上增添了新的條件，所以想弄清楚后面的問題，必須認真的學習并理解問題 1。
0-1 背包問題的 4 種解決方法&&算法策略：https://tyler-zx.blog.csdn.net/article/details/83620475
?
動態規劃概念
動態規劃算法與分治算法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態規劃法求解的問題，經分解得到的子問題往往不是相互獨立的。
該算法的有效性依賴于問題本身所具有的兩個重要性質：最優子結構性質和子問題重疊性質。從一般意義上講，問題所具有的這兩個重要性質是該問題可用動態規劃算法求解的基本要素。這對于在設計求解具體問題的算法時，是否選擇動態規劃算法具有指導意義 。
最優子結構
設計動態規劃算法的第一步通常是要刻畫最優解的結構。當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。問題的最優子結構性質提供了該問題可用動態規劃算法求解的重要線索。利用問題的最優子結構性質，以自底向上的方式遞歸地從子問題的最優解逐步構造出整個問題的最優解。
重疊子問題
可用動態規劃算法求解的問題應具備的另一基本要素是子問題的重疊性質。在用遞歸算法自頂向下解此問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數時間查看一下結果。通常，不同的子問題個數隨問題的大小呈多項式增長。因此，用動態規劃算法通常只需要多項式時間，從而獲得較高的解題效率。
備忘錄方法
備忘錄方法是動態規劃算法的變形。與動態規劃算法一樣，備忘錄方法用表格保存已解決的子問題的答案，在下次需要解此子問題時，只要簡單地查看該子問題的解答，而不必重新計算。與動態規劃算法不同的是，備忘錄方法的遞歸方式是自頂向下，而動態規劃算法則是自底向上遞歸的。因此備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。
動態規劃算法適用于解最優化問題。通?？砂匆韵?個步驟設計：
(1)找出最優解的性質，并刻畫其結構特征。 (2)遞歸地定義最優值。 (3)以自底向上的方式計算出最優值。 (4)根據計算最優值時得到的信息，構造最優解。?
?
問題1：0-1背包問題
? ? ??
動態規劃解 0-1 背包問題的基本思想：
對于每個物品我們可以有兩個選擇，放入背包，或者不放入，有 n 個物品，故而我們需要做出 n 個選擇，于是我們設 F[i][v] 表示做出第 i 次選擇后，所選物品放入一個容量為 v 的背包獲得的最大價值。現在我們來找出遞推公式，對于第 i 件物品，有兩種選擇，放或者不放。
① 如果放入第 i 件物品，則 F[i][v] = F[ i-1 ][ v-w[i] ] + p[i] ，表示，前 i-1 次選擇后所選物品放入容量為 v-w[i] 的背包所獲得最大價值為?F[ i-1 ][ v-w[i] ]?，加上當前所選的第 i 個物品的價值 p[i] 即為 F[i][v] 。
② 如果不放入第 i 件物品，則有 F[i][v] = F[ i-1 ][ v ]，表示當不選第i件物品時，F[i][v] 就轉化為前 i-1 次選擇后所選物品占容量為 v 時的最大價值 F[i-1][v]。則：F[i][v] = max{ F[ i-1 ][v], F[ i-1 ][ v-w[i] ]?+ p[i] }。
#include <iostream> using namespace std; #define N 1005 int Asd[N][N]; //Asd[i][j]表示前 i 個物品，背包容量是 j 的情況下的最大價值。 int Value[N]; int Vol[N];int main() {int n, Volume;cin >> n >> Volume;for(int i = 1; i <= n; i++)cin >> Vol[i] >> Value[i];for(int i = 1; i <= n; i++) { //n個物品for(int j = 1; j <= Volume; j++) { //Volume是容量 Asd[i][j] = Asd[i-1][j]; if(j >= Vol[i])Asd[i][j] = max(Asd[i][j], Asd[ i-1 ][ j-Vol[i] ] + Value[i]);} }cout << Asd[n][Volume] <<endl;return 0; }?
優化：使用一維數組
其實狀態轉移每次只與上一層有關，所以可以用一維數組記錄狀態，轉移方程：Asd[j] = max(Asd[j], Asd[ j-Vol[i] ] + Value[i]);?，此時第二層循環需要做出響應的變化，即第二層循環需要從大到小循環。
#include<iostream> using namespace std; #define N 1005 int Asd[N]; int Value[N]; int Vol[N];int main() {int n, Volume;cin >> n >> Volume;for(int i = 1; i <= n; i++)cin >> Vol[i] >> Value[i];for(int i = 1; i <= n; i++){for(int j = Volume; j >= Vol[i]; j--)Asd[j] = max(Asd[j], Asd[ j-Vol[i] ] + Value[i]);}cout<< Asd[Volume] <<endl;return 0; }?
?
問題2：完全背包問題
完全背包問題與?0-1 背包問題的區別在于完全背包問題中的物品可選無限次。
? ? ??
也是兩種情況，選或不選，只不過每次可以選無限次，所以在 0-1 背包的基礎上把
Asd[i][j] = max(Asd[i][j], Asd[ i-1 ][ j-Vol[i] ] + Value[i]);? ? ?改為： Asd[i][j] = max(Asd[i][j], Asd[ i ][ j-Vol[i] ] + Value[i]);
#include <iostream> using namespace std; #define N 1005 int Asd[N][N]; //Asd[i][j]表示前 i 個物品，背包容量是 j 的情況下的最大價值。 int Value[N]; int Vol[N];int main() {int n, Volume;cin >> n >> Volume;for(int i = 1; i <= n; i++)cin >> Vol[i] >> Value[i];for(int i = 1; i <= n; i++) { //n個物品for(int j = 1; j <= Volume; j++) { //Volume是容量Asd[i][j] = Asd[i-1][j]; if(j >= Vol[i]) Asd[i][j] = max(Asd[i][j], Asd[ i ][ j-Vol[i] ] + Value[i]);} }cout << Asd[n][Volume] <<endl;return 0; }優化：一維數組 #include<iostream> using namespace std; #define N 1005 int Asd[N]; int Value[N]; int Vol[N];int main() {int n, Volume;cin >> n >> Volume;for(int i = 1; i <= n; i++)cin >> Vol[i] >> Value[i];for(int i = 1; i <= n; i++){for(int j = Vol[i]; j <= Volume; j++)Asd[j] = max(Asd[j], Asd[ j-Vol[i] ] + Value[i]);}cout<< Asd[Volume] <<endl;return 0; }?
?
問題3：多重背包問題
多重背包問題與?0-1 背包問題的區別在于多重背包問題中的物品數不唯一。
? ? ??
?
方法１：O(n^3) 解法
加一層循環?，把 s?個物品的每種選擇情況都嘗試一遍，如果不拿，則還是 0-1 背包問題中不選擇的情況。
#include <iostream> using namespace std; #define N 1005 int Asd[N][N]; //Asd[i][j]表示前 i 個物品，背包容量是 j 的情況下的最大價值。 int Value[N], Vol[N], S[N];int main() {int n, Volume;cin >> n >> Volume;for(int i = 1; i <= n; i++)cin >> Vol[i] >> Value[i] >> S[i];for(int i = 1; i <= n; i++) { //n個物品for(int j = 1; j <= Volume; j++) { //Volume是容量for(int k = 1; k <= S[i] && j >= k*Vol[i]; k++){Asd[i][j] = Asd[i-1][j]; if(j >= Vol[i]) Asd[i][j] = max(Asd[i][j], Asd[ i-1 ][ j- k*Vol[i] ] + k*Value[i]);}} }cout << Asd[n][Volume] <<endl;return 0; }優化：一維數組 #include <iostream> using namespace std; #define N 1005 int Asd[N]; int Value[N]; int Vol[N]; int S[N];int main() {int n, Volume;cin >> n >> Volume;for(int i = 1; i <= n; i++)cin >> Vol[i] >> Value[i] >> S[i];for(int i = 1; i <= n; i++){for(int j = Volume; j >= Vol[i]; j--){for(int k = 1; k <= S[i] && j >= k*Vol[i]; k++)Asd[j] = max(Asd[j], Asd[ j - k*Vol[i] ] + k*Value[i]);} }cout<< Asd[Volume] <<endl;return 0; }?
方法2：二進制優化
除了上面的方法外，我們可以換一種思路。這個題目給的物品數量不是唯一的，所以我們可以把一個物品的 S 份全放到數組中。即：第 i 個物品有 S 個，那么就可以將每個物品的容量和價值復制 S 份。例如：一個物品的容量是 2，價值是 3，有 5 個，那么就可以將 [Volume:2 ?Value:3] 這一條信息插入 5 次。這樣就把多重背包問題轉換成了最初的 0-1 背包問題，直接套用 0-1 背包問題即可解決該問題。
但是這樣做會增加問題的規模，時間復雜度仍然很高。此時需要用到二進制的思想。例如：數字 7 寫成二進制形式是：111，意思是 7?= 1?+ 2?+ 4。對于一個有 7 份的物品而言，可以不拿( 0-1背包問題，不取就行了 )，可以拿以下這幾種情況：
拿1個，即取１ ????? 拿2個，即取2 ??? 拿3個，即為：3 = 1+2 ? 拿4個，即為：4 ?? 拿5個，即為：5 = 1+4 ?? 拿6個，即為：6 = 2+4 拿7個，即為：7 = 1+2+4按照原來的思路是將這個物品拆成一個一個的，需要將信息插入 7 次。而使用二進制的思想，只需要插入 3?條信息即可，這樣做的好處是減少了問題的規模。
第一條：[Volume:2 ?Value:3] 第二條：[Volume:2*2 ?Value:3*2] 第三條：[Volume:2*4 ?Value:3*4]比較特殊的情況，例如物品的份數是 10。如果按照二進制表示需要 4 位，但是 4 位二進制能表示 0-15，但是該物品并沒有那么多。所以此時依然會使用 7 的表示方法，只是加上一條信息：[ Volume:2*3 ?Value:3*3 ]就可以表示 10 個物品，且不會超過物品的數量。從 1 到 10 的取法這里就不再贅述了。
#include <iostream> #include <vector> using namespace std; #define N 1005 int Asd[N]; int n, Volume; struct Good {int volume;int value; };int main() {vector<Good> goods;cin >> n >> Volume;for(int i = 1; i <= n; i++){int volume, value, s;cin >> volume >> value >> s;for(int k = 1; k <= s; k *= 2){s -= k;goods.push_back({volume*k, value*k});}if(s > 0) goods.push_back({volume*s, value*s});}for(auto good: goods){for(int j = Volume; j >= good.volume; j--)Asd[j] = max(Asd[j], Asd[ j - good.volume ] + good.value);}cout<< Asd[Volume] <<endl;return 0; }?
?
問題4：混合背包問題
混合背包問題是前幾種背包問題的組合。對于混合背包，需要將該問題拆成多重背包和完全背包問題，然后再求解。
? ? ??
#include <iostream> #include <vector> using namespace std; const int N = 1010;struct Thing {int kind;int volume, value; };int n, Volume; vector<Thing> things; int Asd[N];int main() {cin >> n >> Volume;for(int i = 1; i <= n; i++){int volume, value, s;cin >> volume >> value >> s;if(s < 0) things.push_back({1, volume, value});else if(s == 0) things.push_back({0, volume, value});else{for(int k = 1; k <= s; k <<= 1){s -= k;things.push_back({1, volume*k, value*k});}if(s) things.push_back({1, volume*s, value*s});}}for(auto &thing: things){if(thing.kind == 1){for(int i = Volume; i >= thing.volume; i--)Asd[i] = max(Asd[i], Asd[ i - thing.volume ] + thing.value); }else{ //無限物品for(int i = thing.volume; i <= Volume; i++)Asd[i] = max(Asd[i], Asd[ i - thing.volume ] + thing.value);}}cout<< Asd[Volume] <<endl;return 0; }?
?
問題5：二維背包問題
二維背包問題是加了一個重量的限制，該問題可以用遞歸的方法完成，遞歸方法的優點是易于理解，缺點是不適合應用于數據量較大的情況下，當數據量過大時會 Time Limit Exceeded。
? ? ? ?
?
方法1：遞歸
#include <iostream> #include <cstdio> using namespace std; #define N 100struct goods {int volume; //物品體積int weight; //物品重量int value; //物品價值 };int n, bestValue, cvalue, cweight, cvolume, C, D; //物品數量，價值最大，當前價值，當前重量，當前容量，背包容量C，背包重量D goods goods[N];int Force(int i){if(i > n-1) //結束遞歸的條件，不超過重量和容量的限制，且價值最大{if(bestValue < cvalue && cweight <= D && cvolume <= C)bestValue = cvalue;return bestValue;}//拿cweight += goods[i].weight;cvalue += goods[i].value;cvolume += goods[i].volume;if(cweight <= D && cvolume <= C)Force(i+1);//不拿cweight -= goods[i].weight;cvalue -= goods[i].value;cvolume -= goods[i].volume;Force(i+1);return bestValue; }int main() {cin >> n >> C >> D;for(int i = 0; i < n; i++)cin >> goods[i].volume >> goods[i].weight >> goods[i].value;int sum1 = Force(0);cout << sum1 <<endl;return 0; }?
方法2：動態規劃
#include <iostream> using namespace std; #define N 1005 int Asd[N][N]; int Value[N]; int Vol[N]; int W[N];int main() {int n, Volume, Weight;cin >> n >> Volume >> Weight;for(int i = 1; i <= n; i++)cin >> Vol[i] >> W[i] >> Value[i];for(int i = 1; i <= n; i++){for(int j = Volume; j >= Vol[i]; j--){for(int k = Weight; k >= W[i]; k--)Asd[j][k] = max(Asd[j][k], Asd[ j - Vol[i] ][ k - W[i] ] + Value[i]);}}cout<< Asd[Volume][Weight] <<endl;return 0; }?
?
問題6：分組背包問題
分組背包問題是一組物品中只能選擇一個，若一組有n個物品，則有 n+1 種決策(不選 + n種選擇可能)。結局方法是加一層決策層，循環組內物品，判斷是否選擇該組內的物品，以及選擇哪一個。其實上面的問題都可以理解成：循環物品，循環容量，循環決策這三步。
? ? ??
#include <iostream> using namespace std; #define N 1005 int Asd[N]; int Value[N]; int Vol[N];int main() {int n, Volume, Group; //Group是組內物品的數量cin >> n >> Volume;for(int i = 1; i <= n; i++) //第一層循環，循環物品{cin >> Group;for(int j = 0; j < Group; j++)cin >> Vol[j] >> Value[j];for(int j = Volume; j >= 0; j--) //第二層循環，循環體積for(int k = 0; k < Group; k++) //加一層循環，在做決策的時候選擇組內的物品if(j >= Vol[k])Asd[j] = max(Asd[j], Asd[ j - Vol[k] ] + Value[k]);}cout<< Asd[Volume] <<endl;return 0; }?
?
問題7：有依賴的背包問題?(困難)
?? ? ??
?
?
問題8：背包問題求方案數
? ? ??
?
?
問題9：背包問題求具體方案
還是 0-1 背包問題，只不過是需要求出價值最大時，選擇的物品的方案。此時需要使用數組來記錄選擇的物品的編號。
? ? ??
#include <iostream> #include <cstdio> #define N 100 #define MAX(a,b) a < b ? b : a using namespace std;struct goods{int volume;//物品重量int value;//物品價值 };int n, cv, cw, Volume; //物品數量，價值最大，當前價值，當前重量，背包容量 int X[N],cx[N]; //最終存儲狀態，當前存儲狀態 goods goods[N];int Bag(int n, struct goods a[], int Volume, int x[]){int V[N][N+1];for(int i = 1; i <= n; i++)for(int j = 1; j <= Volume; j++)if(j < a[i].volume)V[i][j] = V[i-1][j];elseV[i][j] = max(V[i-1][j],V[i-1][ j-a[i].volume ] + a[i].value);for(int i = n, j = Volume; i > 0; i--){if(V[i][j] > V[i-1][j]){x[i-1] = 1;j = j - a[i].volume;}elsex[i-1] = 0;}return V[n][Volume]; }int main() {cin >> n >> Volume;for(int i = 1; i <= n; i++){cin >> goods[i].volume >> goods[i].value;}int sum = Bag(n, goods, Volume, X);cout << "動態規劃法求解 0/1 背包問題:\nX=[ ";for(int i = 0; i < n; i++)cout << X[i] <<" "; //輸出所求X[n]矩陣printf("] 裝入總價值[%d]\n", sum);return 0; }?
題目來源于AcWing題庫：AcWing
學習視頻：背包前6講、背包后3講
YXC NB!!!
總結
以上是生活随笔為你收集整理的九种 0-1 背包问题详解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 对象存储概述
- 下一篇： BlueStore——先进的用户态文件系