完全背包与多重背包学习笔记
2026-08-06 09:01:56
发布于：广东
完全背包与多重背包学习笔记
一、先用 01 背包找感觉
背包问题的共同模型是：
有一些物品，每个物品有体积和价值。
背包容量有限，不能超过 m。
问最多能装出多少价值。
01 背包中，每个物品只有两种选择：
不选；
选 1 个。
所以 01 背包的核心是：
当前这个物品只能用一次。
二维01背包模板：
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
}
}
一维 01 背包模板：
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]);
}
}
这里最重要的是内层循环：
for (int j = m; j >= w[i]; j--)
它是倒着枚举容量。
为什么要倒着？
因为我们不希望第 i 个物品被重复使用。
当 j 从大到小走时，f[j - w[i]] 还是“没有用过第 i 个物品”的旧状态，所以加上 v[i] 后，只会选一次第 i 个物品。
这句话很关键：
01 背包倒序，是为了防止同一个物品被重复选。
后面学完全背包和多重背包，其实就是在回答一个问题：
当前物品到底能用几次？
二、完全背包：每种物品可以无限选
完全背包和 01 背包的题面很像，但是有一个巨大区别：
01 背包：每个物品最多选 1 次。
完全背包：每种物品可以选很多次，只要容量够。
比如有一种苹果：
体积 2，价值 3。
如果背包容量够，可以选：
0 个、1 个、2 个、3 个……
这就是完全背包。
我们先用二维数组来想，这样更容易理解。
设：
dp[i][j] 表示只考虑前 i 种物品，背包容量为 j 时的最大价值。
现在考虑第 i 种物品。
如果不选第 i 种物品：
dp[i][j] = dp[i - 1][j]
如果选了一个第 i 种物品，会占用 w[i] 的容量，增加 v[i] 的价值。
关键问题来了：
选完一个第 i 种物品后，还能不能继续选第 i 种物品？
完全背包的答案是：
可以。
所以选一个之后，前面的状态应该还是第 i 行：
dp[i][j - w[i]] + v[i]
不是：
dp[i - 1][j - w[i]] + v[i]
因为 dp[i - 1] 表示不能再用第 i 种物品了，而完全背包允许继续用。
所以完全背包普通版转移式是：
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])
完整代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int w[N], v[N];
int dp[N][N];
void solve() {
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 = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= w[i]) {
dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}
cout << dp[n][m] << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
这一版要记住一句话：
完全背包二维转移中，选当前物品时用 dp[i][j - w[i]]，因为当前物品还能继续选。
三、完全背包空间压缩版：一维数组要正序
二维完全背包可以帮助理解，但比赛中更常写一维。
完全背包一维模板：
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}
注意容量 j 是正着枚举：
for (int j = w[i]; j <= m; j++)
这是完全背包最容易和 01 背包混的地方。
为什么完全背包要正序？
因为完全背包允许同一种物品选多次。
当 j 从小到大走时，f[j - w[i]] 可能已经在这一轮被第 i 种物品更新过。
这正好表示：
前面已经选过第 i 种物品，现在可以再选一个。
举个小例子：
物品体积 w = 2，价值 v = 3，容量 m = 6。
正序枚举：
j = 2 时，f[2] 可以选 1 个这个物品。
j = 4 时，f[4] 可以从 f[2] 再加一个这个物品，变成选 2 个。
j = 6 时，f[6] 可以从 f[4] 再加一个这个物品，变成选 3 个。
这就是完全背包“可以重复选”的来源。
完整代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int w[N], v[N];
int f[N];
void solve() {
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 = w[i]; j <= m; j++) {
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}
cout << f[m] << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
把 01 背包和完全背包放在一起看：
| 背包类型 | 当前物品能选几次 | 一维容量循环 |
|---|---|---|
| 01 背包 | 最多 1 次 | 从大到小 |
| 完全背包 | 可以很多次 | 从小到大 |
最重要的区别：
01 背包怕重复选，所以倒序。
完全背包就是要允许重复选，所以正序。
四、多重背包：每种物品有固定数量
多重背包介于 01 背包和完全背包之间。
01 背包：每种物品最多 1 个。
完全背包：每种物品无限多个。
多重背包：每种物品最多 s[i] 个。
例如：
第 1 种物品最多 3 个；
第 2 种物品最多 5 个；
第 3 种物品最多 2 个。
这就是多重背包。
题目通常给：
w[i]：第 i 种物品体积
v[i]：第 i 种物品价值
s[i]：第 i 种物品数量
设：
dp[i][j] 表示只考虑前 i 种物品，容量为 j 时的最大价值。
面对第 i 种物品时，我们不再只是“选或不选”，而是可以选：
0 个、1 个、2 个、……、s[i] 个。
如果选 k 个第 i 种物品：
占用体积：k * w[i]
获得价值：k * v[i]
剩余容量：
j - k * w[i]
剩余容量只能交给前 i - 1 种物品，因为第 i 种物品已经决定选 k 个了。
所以转移是：
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i])
其中 k 要满足：
0 <= k <= s[i]
k * w[i] <= j
完整代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int M = 1010;
int w[N], v[N], s[N];
int dp[N][M];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i] >> s[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= s[i] && k * w[i] <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
}
}
}
cout << dp[n][m] << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
这份代码很好理解，因为它真的在枚举：
第 i 种物品到底拿几个？
但是它有三层循环：
枚举物品 i；
枚举容量 j；
枚举数量 k。
如果 s[i] 很大，就会慢。
五、多重背包二进制优化：把多重背包变成 01 背包
多重背包慢，是因为数量太多时，一个一个枚举很浪费。
二进制优化的核心是：
把 s 个相同物品拆成几组，每组当成一个 01 背包物品。
比如某种物品有 13 个。
不要拆成：
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
这样还是太多。
我们拆成：
1, 2, 4, 6
因为：
1 + 2 + 4 + 6 = 13
这些组可以组合出很多数量：
选 1 个：1
选 2 个：2
选 3 个：1 + 2
选 4 个：4
选 5 个：1 + 4
选 6 个：2 + 4
选 7 个：1 + 2 + 4
选 13 个：1 + 2 + 4 + 6
如果原物品是：
体积 w，价值 v，数量 s
拆出一组 cnt 个后，这组新物品就是：
体积 cnt * w
价值 cnt * v
这组新物品只能选一次，所以它是一个 01 背包物品。
二进制优化代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 20000;
int ww[N], vv[N];
int f[N];
void solve() {
int n, m;
cin >> n >> m;
int cntItem = 0;
for (int i = 1; i <= n; i++) {
int w, v, s;
cin >> w >> v >> s;
int k = 1;
while (k <= s) {
cntItem++;
ww[cntItem] = k * w;
vv[cntItem] = k * v;
s -= k;
k *= 2;
}
if (s > 0) {
cntItem++;
ww[cntItem] = s * w;
vv[cntItem] = s * v;
}
}
for (int i = 1; i <= cntItem; i++) {
for (int j = m; j >= ww[i]; j--) {
f[j] = max(f[j], f[j - ww[i]] + vv[i]);
}
}
cout << f[m] << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
这里后面为什么用倒序？
因为拆出来的每一组只能选一次。
例如 4 个一组，这一组的含义是：
要么拿这一组 4 个；
要么不拿这一组。
不能拿两次这组，否则就变成 8 个了。
所以二进制优化后，本质就是 01 背包：
for (int j = m; j >= ww[i]; j--)
容量必须倒序。
六、最后统一对比
背包题最重要的不是背代码，而是先看清楚：
每种物品到底能选几个？
| 类型 | 每种物品能选几个 | 核心想法 | 一维循环方向 |
|---|---|---|---|
| 01 背包 | 最多 1 个 | 选或不选 | 倒序 |
| 完全背包 | 无限多个 | 选完还能继续选 | 正序 |
| 多重背包普通版 | 最多 s[i] 个 |
枚举选几个 | 三层循环 |
| 多重背包二进制优化 | 最多 s[i] 个 |
拆成若干个 01 物品 | 倒序 |
判断题型时这样看：
每个物品只有一个 -> 01 背包。
每种物品可以无限选 -> 完全背包。
每种物品有数量限制 -> 多重背包。
数量限制很大 -> 多重背包二进制优化。
最容易错的是循环方向：
01 背包：倒序，因为不能重复选。
完全背包：正序，因为允许重复选。
二进制优化后的多重背包：倒序，因为拆出来的每组只能选一次。
课后练习
练习 1：判断背包类型
判断下面题目属于哪种背包：
1. 每个物品只有一个，选或不选。
2. 每种物品数量不限，可以重复选择。
3. 每种物品最多有 s[i] 个。
4. 每种物品最多有 s[i] 个，并且 s[i] 很大。
练习 2：解释循环方向
请用自己的话解释：
为什么 01 背包一维要倒序？
为什么完全背包一维要正序？
为什么多重背包二进制优化后又要倒序？
练习 3：完全背包
有 n 种物品，每种物品可以选无限多个，背包容量为 m，求最大价值。
要求：
先写二维普通版，再写一维空间压缩版。
练习 4：多重背包
有 n 种物品，第 i 种物品最多有 s[i] 个，求最大价值。
要求：
先写普通版，再尝试二进制优化版。
本节课最重要的五句话
- 完全背包和 01 背包最大的区别是：当前物品能不能重复选。
- 完全背包二维转移用
dp[i][j - w[i]]，因为还可以继续选第i种物品。 - 完全背包一维要正序枚举容量。
- 多重背包普通版就是枚举每种物品选几个。
- 多重背包二进制优化是把多个相同物品拆成若干个 01 背包物品。
有帮助，赞一个