背包問題從入門到入土

我在這里介紹4種常見的背包問題，這里我想按易 --> 難程度從01背包，完全背包，分組背包，多重背包的順序介紹。（封面附在最后）

一，01背包問題（后面三個背包問題的基礎）

01背包問題就是從?n 個物品中選取若干個體積為 v[i]?價值為 w[i] 的物品（同一個物品不能重復選），使容量為 V 的背包的價值最大。

1，01背包二維模板代碼

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define M 10005
ll dp[M][M] = { 0 };
int main() {int  n, v, w, V;  cin >> V >> n;for (int i = 1; i <= n; i++) {cin >> v >> w;for (int j = 1; j <= V; j++) {dp[i][j] = dp[i - 1][j];if (j >= v)dp[i][j] = max(dp[i][j], dp[i - 1][j - v] + w);}}cout << dp[n][V];return 0;
}

狀態定義：我們定義 dp[i][j] 為只考慮前 i 個物品時，j 容量能裝下的物品價值總和的最大值

狀態轉移方程：dp[i][j] = max(dp[i][j], dp[i - 1][j - v] + w)

首先我們先繼承上一個狀態 dp[i][j] = dp[i - 1][j] ，然后判斷是否滿足狀態轉移的條件，即是否有空間加入當前的 i 物品，然后進行狀態轉移，其中狀態轉移的基礎是 dp[i - 1][j - v] ，即不包含物品 n （只包含前 n - 1 個物品），空間為 j - v 的最大價值。

2，01背包一維模板代碼

#include<bits/stdc++.h>
using ll = long long int;
using namespace std;
#define M 10005
ll dp[M] = { 0 };
int main() {int V, n, w, v;cin >> V >> n;for (int i = 1; i <= n; i++) {cin >> w >> v;for (int j = V; j >= w; j--)dp[j] = max(dp[j], dp[j - w] + v);}cout << dp[V];return 0;
}

狀態定義：我們定義 dp[j] 為只考慮前 i 個物品時，j 容量能裝下的物品價值總和的最大值

狀態轉移方程：dp[j] = max(dp[j], dp[j - w] + v)

這里的一維模板代碼是二維模板代碼的空間優化，這里需要被理解的主要有兩點，二維壓縮為一維的合理性以及為什么要倒序遍歷 j 。

1，二維壓縮為一維的合理性

我們的最終目的是為了得出最大價值，對于二維代碼來說就是?dp[n][V] ，那其他存儲空間有什么用呢，從代碼中我們我們不難看出我們在狀態繼承和狀態轉移中需要用到其他存儲空間（dp[i][j]）, 那么一維能滿足這兩點嗎？

從狀態繼承來看，如果是一維，那么其實就不存在狀態繼承的問題，因為你在每個狀態上的操作都在同一行（只有一行）；

從狀態轉移來看，既然狀態已經被繼承了，那么我們就完全可以在被繼承的狀態上（舊狀態）的基礎上轉移，這與二維背包的邏輯完全相同。

2，為什么要倒序遍歷 j?

倒序遍歷的根本原因在于01背包的特性：同一個物品不能重復選。

那換句話說，是不是如果不倒序遍歷 j ，也就是正序遍歷 j ，就會重復選同一個物品，答案是：是的。原因在于每個狀態都是從 dp[j - w] 也就是前 w 個狀態繼承過來的，那如果先更新前面的再更新后面的，就會發生狀態轉移的基礎 dp[j] 不再是（舊狀態）而是已經更新過的新狀態（這是一定的），外在表現就是重復選同一個物品（記住后面會考）。

二，完全背包問題

完全背包問題就是從?n 種物品中每種選取若干個體積為 v[i]?價值為 w[i] 的物品（同一種物品能重復選且每種物品的數量無上限），使容量為 V 的背包的價值最大。

1，完全背包二維模板代碼

#include<bits/stdc++.h>
using namespace std;
#define M 10005
int dp[M][M] = { 0 };
int main() {int  n, V, v, w;cin >> n >> V;for (int i = 1; i <= n; i++) {cin >> v >> w;for (int j = 1; j <= V; j++) {dp[i][j] = dp[i - 1][j];if (j >= v)dp[i][j] = max(dp[i][j], dp[i][j - v] + w);}}cout << dp[n][V];return 0;
}

狀態定義：我們定義 dp[i][j] 為只考慮前 i 種物品時，j 容量能裝下的物品價值總和的最大值

狀態轉移方程：dp[i][j] = max(dp[i][j], dp[i][j - v] + w)

首先我們先繼承上一個狀態 dp[i][j] = dp[i - 1][j]，然后判斷是否滿足狀態轉移的條件，即是否有空間加入當前的 i 物品，然后進行狀態轉移，其中狀態轉移的基礎是 dp[i][j - v] ，即包含物品 n （只包含前 n?種物品），空間為 j - v 的最大價值。

不難看出，完全背包模板代碼與01背包模板代碼的區別就在于狀態轉移的基礎，這也取決于完全背包問題的特性：同一種物品能重復選且每種物品的數量無上限。

2，完全背包一維模板代碼

#include<bits/stdc++.h>
using ll = long long int;
using namespace std;
#define M 10005
ll dp[M] = { 0 };
int main() {int n, V, w, v;cin >> n >> V;for (int i = 1; i <= n; i++) {cin >> w >> v;for (int j = w; j <= V; j++)dp[j] = max(dp[j], dp[j - w] + v);}cout << dp[V];return 0;
}

狀態定義：我們定義 dp[j] 為只考慮前 i 種物品時，j 容量能裝下的物品價值總和的最大值

狀態轉移方程：dp[j] = max(dp[j], dp[j - w] + v)

這里的一維模板代碼是二維模板代碼的空間優化，這里需要被理解的主要也有兩點，二維壓縮為一維的合理性以及為什么要正序遍歷 j 。（其中二維壓縮為一維的合理性與01背包問題一致，這里不再贅述，詳見上文）

1，為什么要正序遍歷 j?

正序遍歷的根本原因也在于完全背包的特性：同一種物品能重復選且每種物品的數量無上限。

（詳見01背包）

三，分組背包問題

分組背包問題就是從?n 組物品中每組選取一個體積為 v[i][k]?價值為 w[i][k]?的物品（任意一組物品能且僅能入選其中一個物品），使容量為 V 的背包的價值最大。

（二維模板代碼這里就不展示了，前面已經講過二維壓縮到一維的合理性和原理了，我們直接用最優的）

1，分組背包一維模板代碼

/*題目描述(hdu 1712)
輸入包含多個數據集。
每個數據集的第一行包含兩個正整數 N 和 M，N 表示課程數量，M 表示 ACboy 可用的天數。
接下來是一個矩陣 A[i][j]，（1 <= i <= N <= 100，1 <= j <= M <= 100）。
A[i][j] 表示如果 ACboy 在第 i 門課程上花費 j 天，他將獲得價值為 A[i][j] 的收益。
當 N = 0 且 M = 0 時，輸入結束。
*/
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#define M 105//提交以前記得改數據
using ll = long long int;
using namespace std;int main() {int n, m;while (~scanf("%d %d", &n, &m) && n && m) {int w[M][M];int dp[M] = { 0 };int v[M];for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {cin >> w[i][j];v[j] = j;}	for (int i = 1; i <= n; i++) for (int j = m; j >= 0; j--) //總天數for (int k = 1; k <= j; k++) //付出的天數(k只是一個編號)if (j >= v[k])dp[j] = max(dp[j], dp[j - v[k]] + w[i][k]);cout << dp[m] << endl;}return 0;
}
/*樣例輸入
2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0
*//*樣例輸出
3
4
6
*/

狀態定義：我們定義 dp[j] 為只考慮前 i 組物品時，j 容量能裝下的物品價值總和的最大值

狀態轉移方程：dp[j] = max(dp[j], dp[j - v[k]] + w[i][k])

這里的一維模板代碼是二維模板代碼的空間優化，這里需要被理解的主要有三點：二維壓縮為一維的合理性（這里不再贅述），為什么要倒序遍歷 j 以及為什么要三層循環。

1，為什么要倒序遍歷 j?

單從這一點來看分組背包一維代碼和01背包一維代碼類似，那是什么導致了這個 “類似” 呢？

我們還是從兩種問題的特性出發：

01背包：同一個物品不能重復選

分組背包：任意一組物品能且僅能入選其中一個物品

大家應該發現了，“一個” 是關鍵，那為什么這一特性會導致倒序呢？

（詳見01背包）

2，為什么要三層循環

這還是取決于分組背包的特性：每組一個。

既然每組只能選一個，我們又要價值最大，那我們就要在容量的范圍內盡可能選最大的，怎么選最大呢，最簡單的思路就是應用選擇排序的原理：打擂臺（價值更大的當擂主，然后一直守擂，知道遇到更大的挑戰者），事實上我們在這里也是這么做的，而這一操作又自成一層循環，加上本來的兩層，2+1=3。

四，多重背包

多重背包問題就是從?n 種物品中每種選取若干個體積為 v?價值為 w?的物品（同一種物品能重復選，每種物品的數量有限），使容量為 V 的背包的價值最大。

思路1：

在展示最優代碼之前我先說一種簡單的方法，把多重背包問題看成是01背包問題，畢竟多重背包問題物品是有限的而且還沒有選取限制，實際上01背包問題是特殊的多重背包問題（每種物品只有一個）。但是特殊情況的解法并不一定能適用于普遍情況，當每種問題的物品太多就會TLE，所以這種方法不推薦用，也就圖一樂。

1，多重背包一維模板代碼

#include<bits/stdc++.h>
using ll = long long int;
using namespace std;
#define M 100005
int dp[M] = { 0 };
int main() {int V, n;cin >> V >> n;for (int i = 0, v, w, s; i < n; i++) {cin >> v >> w >> s;for (int k = 1; s; s -= k, k *= 2) {//把 s 進行二進制拆分，類似于 st 表k = min(s, k);for (int j = V; j >= k * v; j--) dp[j] = max(dp[j], dp[j - k * v] + k * w);}}cout << dp[V];return 0;
}

思路2：

這個代碼一看就知道我為什么要把它放到最后了，要弄懂這個代碼需要一定的 st 表的基礎，那這時候就有兄弟要問了，有沒有不會 st 表也能理解的方法呢，有的兄弟有的，二進制大家都懂吧，任意一個數都能用二進制表示，也就是由1，2，4，8，16，32，64...這些數中的一部分組成的，那么我們還是用沿用思路1，只是在其中加一步

for (int k = 1; s; s -= k, k *= 2) {k = min(s, k);...
}

這一步其實就是把一種問題的所有物品進行整合，整合成 1 * v，2 * v，4 * v，8 * v，16 * v，32 * v，64 * v...，然后從 1 * v 這個部分開始倒序刷表（為什么倒序我就不贅述了），這樣一來不管面對多大的體積 j，我們總有一種合適的組合方式適合 j 。這樣一來我們只要預處理好?1 * v，2 * v，4 * v，8 * v，16 * v，32 * v，64 * v...我們就能以對數階的復雜度進行刷表。