🧑‍💻 文章作者：Iareges
🔗 博客主页：https://blog.csdn.net/raelum
⚠️ 转载请注明出处

目录

• 前言
• 一、01背包
• • 1.1 使用滚动数组优化
• 二、完全背包
• • 2.1 使用滚动数组优化
• 三、多重背包
• • 3.1 使用二进制优化
• 四、分组背包
• 总结

前言

本文主要介绍常见的四种背包问题，思维导图如下：

一、01背包

💡 现有 NNN 件物品和一个最多能承重 MMM 的背包，第 iii 件物品的重量是 wiw_iwi​，价值是 viv_ivi​。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。

因为每件物品只有选与不选两种状态，所以该问题又称01背包问题。

设 dp[i][j]dp[i][j]dp[i][j] 的含义是：在背包承重为 jjj 的前提下，从前 iii 个物品中选能够得到的最大价值。不难发现 dp[N][M]dp[N][M]dp[N][M] 就是本题的答案。

如何计算 dp[i][j]dp[i][j]dp[i][j] 呢？我们可以将它划分为以下两部分：

• 选第 iii 个物品：由于第 iii 个物品一定会被选择，那么相当于从前 i−1i-1i−1 个物品中选且总重量不超过 j−w[i]j-w[i]j−w[i]，对应 dp[i−1][j−w[i]]+v[i]dp[i-1][j-w[i]]+v[i]dp[i−1][j−w[i]]+v[i]。
• 不选第 iii 个物品：意味着从前 i−1i-1i−1 个物品中选且总重量不超过 jjj，对应 dp[i−1][j]dp[i-1][j]dp[i−1][j]。

结合以上两点可得递推公式：

dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−w[i]]+v[i])dp[i][j] = \max(dp[i-1][j],\;dp[i-1][j-w[i]]+v[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])

由于下标不能是负数，所以上述递推公式要求 j≥w[i]j\geq w[i]j≥w[i]。当 j

dp[i][j]={dp[i−1][j],jdp[i−1][j],max(dp[i−1][j],dp[i−1][j−w[i]]+v[i]),​j

dpdpdp 数组应当如何初始化呢？当背包承重为 000 时，显然装不下任何物品，所以 dp[i][0]=0(1≤i≤N)dp[i][0]=0\;(1\leq i\leq N)dp[i][0]=0(1≤i≤N)。若一个物品也不选（即从前 000 个物品中选），此时最大价值也是 000，所以 dp[0][j]=0(0≤j≤M)dp[0][j]=0\;(0\leq j\leq M)dp[0][j]=0(0≤j≤M)。由此可知，dpdpdp 数组应当全0初始化，即声明为全局变量。

题目链接：AcWing 2. 01背包问题

#include using namespace std;const int N = 1010;int w[N], v[N];
int dp[N][N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (j < w[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);}}cout << dp[n][m] << "\n";return 0;
}

时间复杂度为 O(nm)O(nm)O(nm)。

1.1 使用滚动数组优化

之前我们用到的 dpdpdp 数组是二维数组，它可以进一步优化成一维数组。

观察递推公式不难发现，dpdpdp 数组中第 iii 行的元素仅由第 i−1i-1i−1 行的元素得来，即第 000 行元素的更新值放到第 111 行，第 111 行元素的更新值放到第 222 行，以此类推。与其把一行的更新值放到新的一行，不如直接就地更新，因此我们的 dpdpdp 数组只需要一行来存储，即一维数组。

去掉 dpdpdp 数组的第一维后，递推公式变成：

dp[j]={dp[j],jdp[j],max(dp[j],dp[j−w[i]]+v[i]),​j

即

dp[j]=max⁡(dp[j],dp[j−w[i]]+v[i]),j≥w[i]dp[j]= \max(dp[j],\;dp[j-w[i]]+v[i]),\quad j\geq w[i] dp[j]=max(dp[j],dp[j−w[i]]+v[i]),j≥w[i]

原先 jjj 是从 111 遍历至 mmm 的，现在只需从 w[i]w[i]w[i] 遍历至 mmm。但，这个遍历顺序真的对吗？

请看下图：

红色箭头表示，在二维数组中，dp[i][j]dp[i][j]dp[i][j] 由 dp[i−1][j−w[i]]dp[i-1][j-w[i]]dp[i−1][j−w[i]] 和 dp[i−1][j]dp[i-1][j]dp[i−1][j] 得来，dp[i][j+w[i]]dp[i][j+w[i]]dp[i][j+w[i]] 由 dp[i−1][j]dp[i-1][j]dp[i−1][j] 和 dp[i−1][j+w[i]]dp[i-1][j+w[i]]dp[i−1][j+w[i]] 得来。用一维数组的话来讲就是，第 iii 行的 dp[j]dp[j]dp[j] 由第 i−1i-1i−1 行的 dp[j−w[i]]dp[j-w[i]]dp[j−w[i]] 和 dp[j]dp[j]dp[j] 得来，第 iii 行的 dp[j+w[i]]dp[j+w[i]]dp[j+w[i]] 由第 i−1i-1i−1 行的 dp[j]dp[j]dp[j] 和 dp[j+w[i]]dp[j+w[i]]dp[j+w[i]] 得来。

如果 jjj 从小到大遍历，那么会先更新 dp[j]dp[j]dp[j] 再更新 dp[j+w[i]]dp[j+w[i]]dp[j+w[i]]，这就导致在更新 dp[j+w[i]]dp[j+w[i]]dp[j+w[i]] 时使用的是第 iii 行的 dp[j]dp[j]dp[j] 而非第 i−1i-1i−1 行的 dp[j]dp[j]dp[j]，即当 jjj 从小到大遍历时，二维数组的递推式变成了：

dp[i][j]={dp[i−1][j],jdp[i−1][j],max(dp[i−1][j],dp[i][j−w[i]]+v[i]),​j

⚠️ 请牢记该式，后续讲解完全背包时会提到它。

这显然是错误的。事实上，让 jjj 从大到小遍历就不会出现这个问题。

#include using namespace std;const int N = 1010;int w[N], v[N];
int dp[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];for (int i = 1; i <= n; i++)for (int j = m; j >= w[i]; j--)dp[j] = max(dp[j], dp[j - w[i]] + v[i]);cout << dp[m] << "\n";return 0;
}

当然，www 数组和 vvv 数组也是不必要的，我们可以边输入边处理，因此可以得到01背包问题的最终版代码：

#include using namespace std;const int N = 1010;int dp[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {int w, v;cin >> w >> v;for (int j = m; j >= w; j--)dp[j] = max(dp[j], dp[j - w] + v);}cout << dp[m] << "\n";return 0;
}

到此为止，可以总结出，当 dpdpdp 数组是二维数组时，jjj 既可以从小到大遍历也可以从大到小遍历，但当 dpdpdp 数组是一维数组时，jjj 只能从大到小遍历。

二、完全背包

💡 现有 NNN 种物品和一个最多能承重 MMM 的背包，每种物品都有无限个，第 iii 种物品的重量是 wiw_iwi​，价值是 viv_ivi​。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。

设 dp[i][j]dp[i][j]dp[i][j] 的含义是：在背包承重为 jjj 的前提下，从前 iii 种物品中选能够得到的最大价值。

如何计算 dp[i][j]dp[i][j]dp[i][j] 呢？我们可以将它划分为以下若干部分：

• 选 000 个第 iii 种物品：相当于不选第 iii 种物品，对应 dp[i−1][j]dp[i-1][j]dp[i−1][j]。
• 选 111 个第 iii 种物品：对应 dp[i−1][j−w[i]]+v[i]dp[i-1][j-w[i]]+v[i]dp[i−1][j−w[i]]+v[i]。
• 选 222 个第 iii 种物品：对应 dp[i−1][j−2⋅w[i]]+2⋅v[i]dp[i-1][j-2\cdot w[i]]+2\cdot v[i]dp[i−1][j−2⋅w[i]]+2⋅v[i]。
• ⋯\cdots⋯

上述过程并不会无限进行下去，因为背包承重是有限的。设第 iii 种物品最多能选 ttt 个，于是可知 t=⌊jw[i]⌋t=\lfloor \frac{j}{w[i]}\rfloort=⌊w[i]j​⌋，从而得到递推式：

dp[i][j]=max⁡0≤k≤tdp[i−1][j−k⋅w[i]]+k⋅v[i]dp[i][j]=\max_{0\leq k\leq t} dp[i-1][j-k\cdot w[i]]+k\cdot v[i] dp[i][j]=0≤k≤tmax​dp[i−1][j−k⋅w[i]]+k⋅v[i]

题目链接：AcWing 3. 完全背包问题

#include using namespace std;const int N = 1010;int w[N], v[N];
int dp[N][N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {int t = j / w[i];for (int k = 0; k <= t; k++)dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);}cout << dp[n][m] << "\n";return 0;
}

若将 ttt 的值改为 min⁡(1,j/w[i])\min(1,\,j/w[i])min(1,j/w[i])，则完全背包将退化为01背包。

上述代码的时间复杂度为 O(m2∑iwi−1)≈O(m2n)O(m^2\sum_iw_i^{-1})\approx O(m^2n)O(m2∑i​wi−1​)≈O(m2n)，TLE是必然的。

2.1 使用滚动数组优化

考虑 dp[i][j]dp[i][j]dp[i][j]，此时第 iii 种物品最多能选 t1=⌊jw[i]⌋t_1=\lfloor \frac{j}{w[i]} \rfloort1​=⌊w[i]j​⌋ 个，将递推式展开：

dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−w[i]]+v[i],dp[i−1][j−2⋅w[i]]+2⋅v[i],⋮dp[i−1][j−t1⋅w[i]]+t1⋅v[i])\begin{aligned} dp[i][j] = \max(dp[i-1][j],\; &dp[i-1][j-w[i]]+v[i], \\ &dp[i-1][j-2\cdot w[i]]+2\cdot v[i], \\ &\vdots \\ &dp[i-1][j-t_1\cdot w[i]]+t_1\cdot v[i]) \end{aligned} dp[i][j]=max(dp[i−1][j],​dp[i−1][j−w[i]]+v[i],dp[i−1][j−2⋅w[i]]+2⋅v[i],⋮dp[i−1][j−t1​⋅w[i]]+t1​⋅v[i])​

下面考虑 dp[i][j−w[i]]dp[i][j-w[i]]dp[i][j−w[i]]，此时第 iii 种物品最多能选 t2=⌊j−w[i]w[i]⌋=⌊jw[i]−1⌋=t1−1t_2=\lfloor \frac{j-w[i]}{w[i]} \rfloor=\lfloor \frac{j}{w[i]}-1\rfloor=t_1-1t2​=⌊w[i]j−w[i]​⌋=⌊w[i]j​−1⌋=t1​−1 个，相应的递推式为

dp[i][j−w[i]]=max⁡(dp[i−1][j−w[i]],dp[i−1][j−w[i]−w[i]]+v[i],dp[i−1][j−w[i]−2⋅w[i]]+2⋅v[i],⋮dp[i−1][j−w[i]−t2⋅w[i]]+t2⋅v[i])\begin{aligned} dp[i][j-w[i]] = \max(dp[i-1][j-w[i]],\; &dp[i-1][j-w[i]-w[i]]+v[i], \\ &dp[i-1][j-w[i]-2\cdot w[i]]+2\cdot v[i], \\ &\vdots \\ &dp[i-1][j-w[i]-t_2\cdot w[i]]+t_2\cdot v[i]) \end{aligned} dp[i][j−w[i]]=max(dp[i−1][j−w[i]],​dp[i−1][j−w[i]−w[i]]+v[i],dp[i−1][j−w[i]−2⋅w[i]]+2⋅v[i],⋮dp[i−1][j−w[i]−t2​⋅w[i]]+t2​⋅v[i])​

又注意到 t1=t2+1t_1=t_2+1t1​=t2​+1，上式可化简为

dp[i][j−w[i]]=max⁡(dp[i−1][j−w[i]],dp[i−1][j−2⋅w[i]]+v[i],dp[i−1][j−3⋅w[i]]+2⋅v[i],⋮dp[i−1][j−t1⋅w[i]]+(t1−1)⋅v[i])\begin{aligned} dp[i][j-w[i]] = \max(dp[i-1][j-w[i]],\; &dp[i-1][j-2\cdot w[i]]+v[i], \\ &dp[i-1][j-3\cdot w[i]]+2\cdot v[i], \\ &\vdots \\ &dp[i-1][j-t_1\cdot w[i]]+(t_1-1)\cdot v[i]) \end{aligned} dp[i][j−w[i]]=max(dp[i−1][j−w[i]],​dp[i−1][j−2⋅w[i]]+v[i],dp[i−1][j−3⋅w[i]]+2⋅v[i],⋮dp[i−1][j−t1​⋅w[i]]+(t1​−1)⋅v[i])​

将该式与 dp[i][j]dp[i][j]dp[i][j] 的递推式比较不难发现

dp[i][j]=max⁡(dp[i−1][j],dp[i][j−w[i]]+v[i])dp[i][j]=\max(dp[i-1][j],\;dp[i][j-w[i]]+v[i]) dp[i][j]=max(dp[i−1][j],dp[i][j−w[i]]+v[i])

根据1.1节中的结论，该式对应的是 jjj 从小到大遍历，于是我们只需把01背包问题的代码中的 jjj 改为从小到大遍历即可。

#include using namespace std;const int N = 1010;int dp[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {int w, v;cin >> w >> v;for (int j = w; j <= m; j++)  // 只需修改这一行dp[j] = max(dp[j], dp[j - w] + v);}cout << dp[m] << "\n";return 0;
}

优化后的时间复杂度为 O(nm)O(nm)O(nm)。

三、多重背包

💡 现有 NNN 种物品和一个最多能承重 MMM 的背包，第 iii 种物品的数量是 sis_isi​，重量是 wiw_iwi​，价值是 viv_ivi​。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。

回顾完全背包问题的暴力解法，在背包承重为 jjj 的前提下，第 iii 种物品最多能放 t=j/w[i]t=j/w[i]t=j/w[i] 个（这里是整除）。而在01背包问题中，第 iii 种物品只有一个，所以应当取 t=min⁡(1,j/w[i])t=\min(1,\,j/w[i])t=min(1,j/w[i])。由此可见，对于多重背包问题，只需取 t=min⁡(s[i],j/w[i])t=\min(s[i],\,j/w[i])t=min(s[i],j/w[i])。

对完全背包问题的暴力解法做一点简单修改即可求解多重背包问题。

题目链接：AcWing 4. 多重背包问题

#include using namespace std;const int N = 110;int dp[N][N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {int w, v, s;cin >> w >> v >> s;for (int j = 1; j <= m; j++) {int t = min(s, j / w);  // 只有这里需要修改for (int k = 0; k <= t; k++)dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w] + k * v);}}cout << dp[n][m] << "\n";return 0;
}

时间复杂度为 O(m∑isi)O(m\sum_i s_i)O(m∑i​si​)，但还可以进一步优化。

3.1 使用二进制优化

从时间复杂度的表达式可以看出，O(m)O(m)O(m) 的部分已经无法再优化了，我们只能从 O(∑isi)O(\sum_i s_i)O(∑i​si​) 入手。

先来看一个例子。水果店里有 404040 个苹果，小明计划购买 n(1≤n≤40)n\,(1\leq n\leq 40)n(1≤n≤40) 个苹果，试问如何让小明尽可能快速地完成购买？一个显而易见的暴力做法是，让小明一个个拿（单位是个），但效率过于低下。事实上，店员可事先准备好 666 个箱子，每个箱子中的苹果数量分别为 [1,2,4,8,16,9][1,2,4,8,16,9][1,2,4,8,16,9]，再让小明按箱子拿（单位是箱子），无论小明计划购买多少个，他最多只需要拿 666 次，而在暴力做法中，小明最多需要拿 404040 次。

下面用数学语言来描述上面的例子。对于任意的正整数 sss，我们都可以找到 ⌊log⁡2s⌋+1≜k\lfloor \log_2 s\rfloor+1\triangleq k⌊log2​s⌋+1≜k 个正整数 a1,⋯,aka_1,\cdots,a_ka1​,⋯,ak​，使得 ∀n∈[0,s]\forall\, n\in[0,s]∀n∈[0,s]，都有

n=vTa,a=(a1,⋯,ak)T,ai={2i−1,1≤i≤k−1s−2k−1+1(∈[1,2k−1]),i=kn=v^\mathrm{T}a,\quad a=(a_1,\cdots,a_k)^\mathrm{T},\quad a_i= \begin{cases} 2^{i-1},&1\leq i\leq k -1\\ s-2^{k-1}+1\,(\in [1,\,2^{k-1}]),&i=k\\ \end{cases} n=vTa,a=(a1​,⋯,ak​)T,ai​={2i−1,s−2k−1+1(∈[1,2k−1]),​1≤i≤k−1i=k​

其中 v=(v1,⋯,vk)Tv=(v_1,\cdots,v_k)^\mathrm{T}v=(v1​,⋯,vk​)T，且其分量非 000 即 111。

感兴趣的读者可自行证明，这里不再赘述。回到本题，先不考虑背包的承重，我们在暴力求解多重背包的时候，对于每种物品 iii，都要从 000 逐个枚举至 s[i]s[i]s[i]，效率无疑是低下的。现在，对于每种物品 iii，我们将这 s[i]s[i]s[i] 个物品分散至 ⌊log⁡2s[i]⌋+1\lfloor \log_2 s[i]\rfloor+1⌊log2​s[i]⌋+1 个「箱子」中，于是多重背包便化成了01背包。

题目链接：AcWing 5. 多重背包问题 II

多重背包问题中的一个「箱子」相当于01背包问题中的一件「物品」，因此我们需要估计出多重背包问题中到底有多少个箱子。显然箱子总数为

N=∑i=1n(⌊log⁡2s[i]⌋+1)≤∑i=1n⌊log⁡22000⌋+n=11n≤11000N=\sum_{i=1}^n(\lfloor \log_2 s[i]\rfloor+1)\leq \sum_{i=1}^n \lfloor \log_2 2000\rfloor+n=11n\leq 11000 N=i=1∑n​(⌊log2​s[i]⌋+1)≤i=1∑n​⌊log2​2000⌋+n=11n≤11000

#include using namespace std;const int N = 11010, M = 2010;int w[N], v[N];
int dp[M];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;int cnt = 0;while (n--) {int a, b, s;  // a是重量, b是价值, c是数量cin >> a >> b >> s;for (int k = 1; k <= s; k *= 2) {cnt++;w[cnt] = a * k, v[cnt] = b * k;s -= k;}if (s > 0) {cnt++;w[cnt] = a * s, v[cnt] = b * s;}}n = cnt;for (int i = 1; i <= n; i++)for (int j = m; j >= w[i]; j--)dp[j] = max(dp[j], dp[j - w[i]] + v[i]);cout << dp[m] << "\n";return 0;
}

优化后的时间复杂度为 O(m∑ilog⁡si)O(m\sum_i \log s_i)O(m∑i​logsi​)。

四、分组背包

💡 现有 NNN 组物品和一个最多能承重 MMM 的背包，每组物品有若干个，同一组内的物品最多只能选一个。每件物品的重量是 wijw_{ij}wij​，价值是 vijv_{ij}vij​，其中 iii 是组号，jjj 是组内编号。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。

设 dp[i][j]dp[i][j]dp[i][j] 的含义是：在背包承重为 jjj 的前提下，从前 iii 组物品中选能够得到的最大价值。

如何计算 dp[i][j]dp[i][j]dp[i][j] 呢？我们可以将它划分为以下若干部分：

• 不选第 iii 组的物品：对应 dp[i−1][j]dp[i-1][j]dp[i−1][j]。
• 选第 iii 组的第 111 个物品：对应 dp[i−1][j−w[i][1]]+v[i][1]dp[i-1][j-w[i][1]]+v[i][1]dp[i−1][j−w[i][1]]+v[i][1]。
• 选第 iii 组的第 222 个物品：对应 dp[i−1][j−w[i][2]]+v[i][2]dp[i-1][j-w[i][2]]+v[i][2]dp[i−1][j−w[i][2]]+v[i][2]。
• ⋯\cdots⋯
• 选第 iii 组的第 s[i]s[i]s[i] 个物品：对应 dp[i−1][j−w[i][s[i]]]+v[i][s[i]]dp[i-1][j-w[i][s[i]]]+v[i][s[i]]dp[i−1][j−w[i][s[i]]]+v[i][s[i]]。

直接将 dpdpdp 数组优化到一维可得递推式：

dp[j]=max⁡(dp[j],max⁡1≤k≤s[i]dp[j−w[i][k]]+v[i][k])dp[j]=\max(dp[j],\;\max_{1\leq k\le s[i]} dp[j-w[i][k]]+v[i][k]) dp[j]=max(dp[j],1≤k≤s[i]max​dp[j−w[i][k]]+v[i][k])

题目链接：AcWing 9. 分组背包问题

#include using namespace std;const int N = 110;int w[N][N], v[N][N], s[N];
int dp[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> s[i];for (int j = 1; j <= s[i]; j++)cin >> w[i][j] >> v[i][j];}for (int i = 1; i <= n; i++)for (int j = m; j >= 1; j--)for (int k = 1; k <= s[i]; k++)if (j >= w[i][k])dp[j] = max(dp[j], dp[j - w[i][k]] + v[i][k]);cout << dp[m] << "\n";return 0;
}

总结

我们可以用一个公式来表示01背包、完全背包和多重背包：

dp[i][j]=max⁡0≤k≤tdp[i−1][j−k⋅w[i]]+k⋅v[i],t={min⁡(1,j/w[i]),01背包min⁡(+∞,j/w[i])=j/w[i],完全背包min⁡(s[i],j/w[i]),多重背包dp[i][j]=\max_{0\leq k\leq t} dp[i-1][j-k\cdot w[i]]+k\cdot v[i],\quad t=\begin{cases} \min(1,\;j/w[i]),&01背包\\ \min(+\infty,\;j/w[i])=j/w[i],&完全背包 \\ \min(s[i],\;j/w[i]),&多重背包 \end{cases} dp[i][j]=0≤k≤tmax​dp[i−1][j−k⋅w[i]]+k⋅v[i],t=⎩⎨⎧​min(1,j/w[i]),min(+∞,j/w[i])=j/w[i],min(s[i],j/w[i]),​01背包完全背包多重背包​