【GESP】C++六级练习 luogu-B2174, 完全背包
GESP C++六级练习。完全背包DP模板题，是学习动态规划背包系列的入门必刷题。本题直接对应完全背包的标准模型，适合初次接触背包DP的同学理解状态定义、转移方程以及正序遍历的含义。难度⭐⭐。洛谷难度等级普及-。
B2174 完全背包
题目要求
题目描述
你有一个容量为 $V$ 的背包，以及 $n$ 种物品。第 $i$ 种物品的体积为 $w_i$，价值为 $val_i$。
每种物品都有无限件，你可以选择任意多件放入背包，但总容量不能超过 $V$。
请你求出在不超过背包容量的前提下，能获得的最大总价值。
形式化题意：设第 $i$ 种物品选择 $x_i$ 件（$x_i$ 为非负整数），则需要满足： \(\sum_{i=1}^{n} x_i \cdot w_i \le V,\quad x_i \ge 0\) 最大化目标： \(\max \sum_{i=1}^{n} x_i \cdot val_i\)
输入格式
第一行两个整数 $n, V$，表示物品种类数与背包容量。
接下来 $n$ 行，每行两个整数 $w_i, val_i$，分别表示第 $i$ 种物品的体积与价值。
输出格式
输出一个整数，表示最大总价值。
输入输出样例 #1
输入 #1
1
2
3
4
3 10
2 3
3 4
4 5
输出 #1
1
15
说明/提示
样例说明 #1
一种最优方案是选择第 1 种物品 $5$ 件：
- 总体积 $5 \times 2 = 10 \le 10$
- 总价值 $5 \times 3 = 15$
数据范围
对于 $40\%$ 的数据，$1\le n \le 8$，$1\le V \le 12$，且对所有 $i$，$1\le w_i \le 1000$，$0\le val_i \le 1000$。
对于 $100\%$ 的数据，$1\le n \le 1000$，$1\le V \le 1000$，且对所有 $i$，$1\le w_i \le 1000$，$0\le val_i \le 1000$。
题目分析
本题是完全背包问题的标准模板题。如果你已经理解了 01 背包或者刚做完六级真题中的「条形蛋糕」（P17012），那么本题可以帮助你进一步巩固完全背包的模型——事实上，条形蛋糕本质上就是一个完全背包问题的等价建模。
1. 01 背包 vs 完全背包：区别在哪？
在 01 背包 中，每种物品只有 1 件，选了就没了；在 完全背包 中，每种物品有无限件，同一种物品可以反复选取。
两者的状态定义完全一样，但转移时的遍历顺序不同：
| 对比项 | 01 背包 | 完全背包 |
|---|---|---|
| 每种物品可选数量 | 最多 $1$ 件 | 无限件 |
| 一维 DP 遍历容量的方向 | 从大到小（逆序） | 从小到大（正序） |
仅仅是内层循环方向的一字之差，就从”每种物品最多选一件”变成了”每种物品可选无限件”。下文会详细解释其中的原理。
2. 状态定义
定义 $dp[j]$ 表示：背包容量为 $j$ 时，能获得的最大总价值。
初始状态：$dp[0] = 0$，其余全为 $0$（表示什么都不装时价值为 $0$）。
3. 状态转移方程
对于第 $i$ 种物品（体积 $w_i$，价值 $val_i$），对每个容量 $j$（$w_i \le j \le V$）：
\[dp[j] = \max(dp[j],\ dp[j - w_i] + val_i)\]方程含义：面对容量 $j$，我们有两种选择：
- 不选第 $i$ 种物品：价值保持 $dp[j]$ 不变
- 选一件第 $i$ 种物品：腾出 $w_i$ 的空间后，剩余容量 $j - w_i$ 的最大价值为 $dp[j - w_i]$，加上本件价值 $val_i$
取两者的最大值。
4. 从二维到一维——如何理解一维 $dp[j]$ 的含义？
如果你觉得二维 $dp[i][j]$ 很直观，但一维 $dp[j]$ 突然就看不懂了，那是因为这中间缺了一个推导过程。
二维 DP 的完整图景
二维数组 $dp[i][j]$ 是一张 $(n+1) \times (V+1)$ 的表格。外层循环从第 $1$ 行填到第 $n$ 行，每一行代表”考虑前 $i$ 种物品时各容量的最优解”。
关键观察：填第 $i$ 行时，只需要读第 $i-1$ 行的数据（对于 01 背包）或第 $i-1$ 行和第 $i$ 行已填好的部分（对于完全背包）。更早的第 $1, 2, \ldots, i-2$ 行在填第 $i$ 行时已经完全用不到了。
既然旧行用不到，那就不存了
这就像考试交卷——交完上一科的试卷就可以丢掉草稿纸了，下一科重新用同一张纸。
我们只保留一行，让这一行在外层循环的每一轮中被”原地覆盖更新”：
- 外层循环开始处理第 $1$ 种物品之前：$dp[j]$ 全为 $0$，等价于 $dp[0][j]$（不考虑任何物品）
- 处理完第 $1$ 种物品之后：$dp[j]$ 被覆盖为 $dp[1][j]$（只考虑前 $1$ 种物品的最优解）
- 处理完第 $2$ 种物品之后：$dp[j]$ 被覆盖为 $dp[2][j]$（只考虑前 $2$ 种物品的最优解）
- ……
- 处理完第 $n$ 种物品之后：$dp[j]$ 被覆盖为 $dp[n][j]$（考虑全部 $n$ 种物品的最优解）
一维 $dp[j]$ 的真正含义
所以，一维 $dp[j]$ 并不是一个”固定含义”的状态——它的含义随着外层循环的推进而变化：
在外层循环处理完前 $k$ 种物品之后，$dp[j]$ 的含义等价于 $dp[k][j]$，即”只考虑前 $k$ 种物品、背包容量为 $j$ 时的最大总价值”。
当整个外层循环结束时（$k = n$），$dp[V]$ 就等价于 $dp[n][V]$，即最终答案。
理解了这一点之后，下面讨论的”正序/逆序遍历”就容易理解了——它解决的是：在覆盖更新的过程中，如何保证读到的是正确的值？
5. 正序 vs 逆序遍历——一个方向的差别，为什么结果完全不同？
这是理解背包 DP 的最核心要点。
从二维 DP 的转移方程说起
要理解一维 DP 中遍历方向的逻辑，最好的切入点是先回到二维 DP 的转移方程，看看 01 背包和完全背包在逻辑上到底有什么不同。
01 背包的二维转移方程：
\[dp[i][j] = \max(dp[i-1][j],\ dp[i-1][j - w_i] + val_i)\]完全背包的二维转移方程：
\[dp[i][j] = \max(dp[i-1][j],\ dp[i][j - w_i] + val_i)\]唯一的区别在于”选一件”时查找剩余容量的最优值用的是哪一行：
- 01 背包用 $dp[i-1][j - w_i]$：剩余容量 $j - w_i$ 的最优方案不包含物品 $i$ → 我选的这一件就是唯一的一件
- 完全背包用 $dp[i][j - w_i]$：剩余容量 $j - w_i$ 的最优方案可能已经包含了若干件物品 $i$ → 我在已有的基础上再加一件，自然就实现了无限选取
这就是两种背包在算法逻辑上的本质区别。
一维压缩时，遍历方向如何实现这个逻辑？
当我们把二维数组压缩成一维时，$dp[j]$ 在不同时刻代表不同含义：
- 更新前：$dp[j]$ 保存的是”上一轮”的值，即 $dp[i-1][j]$
- 更新后：$dp[j]$ 被覆盖为”本轮”的值，即 $dp[i][j]$
因此，问题变成了：当我们计算 $dp[j]$ 时，$dp[j - w]$ 处于”更新前”还是”更新后”？
- 逆序遍历（从大到小）：$j$ 从大到小处理，而 $j - w < j$，所以 $dp[j - w]$ 还没轮到更新，保存的仍是上一轮的值 $dp[i-1][j-w]$ → 对应 01 背包的转移方程
- 正序遍历（从小到大）：$j$ 从小到大处理，而 $j - w < j$，所以 $dp[j - w]$ 已经被更新过，保存的是本轮的值 $dp[i][j-w]$ → 对应完全背包的转移方程
总结：遍历方向决定了 $dp[j - w]$ 读到的是”旧行”还是”新行”的数据，从而精确地实现了两种背包各自的转移逻辑。
一句话概括：逆序遍历让 $dp[j-w]$ 保持为 $dp[i-1][j-w]$（不含物品 $i$）→ 最多选一次；正序遍历让 $dp[j-w]$ 变为 $dp[i][j-w]$（可能已含物品 $i$）→ 允许无限选取。
用同一组数据验证
理解了上面的逻辑后，我们用具体数据来验证。假设只有一种物品：体积 $w = 2$，价值 $val = 3$，背包容量 $V = 6$。初始 $dp$ 数组全为 $0$。
正序遍历（完全背包）—— $j$ 从 $2$ 到 $6$：
| 步骤 | 更新 $dp[j]$ | 读取 $dp[j-2]$ | 该值是否已被本轮更新？ | 更新后 $dp[j]$ | 实际效果 |
|---|---|---|---|---|---|
| ① | $dp[2]$ | $dp[0] = 0$ | 否（边界值） | $0 + 3 = 3$ | 选了 $1$ 件 |
| ② | $dp[4]$ | $dp[2] = 3$ | ✅ 是（步骤①刚更新） | $3 + 3 = 6$ | 选了 $2$ 件 |
| ③ | $dp[6]$ | $dp[4] = 6$ | ✅ 是（步骤②刚更新） | $6 + 3 = 9$ | 选了 $3$ 件 |
$dp[j - 2]$ 读到的是本轮新值（即 $dp[i][j-2]$），所以每一步都”站在前一步的肩膀上”，物品被不断叠加。
逆序遍历（01 背包）—— $j$ 从 $6$ 到 $2$：
| 步骤 | 更新 $dp[j]$ | 读取 $dp[j-2]$ | 该值是否已被本轮更新？ | 更新后 $dp[j]$ | 实际效果 |
|---|---|---|---|---|---|
| ① | $dp[6]$ | $dp[4] = 0$ | ❌ 否（还没轮到） | $0 + 3 = 3$ | 选了 $1$ 件 |
| ② | $dp[4]$ | $dp[2] = 0$ | ❌ 否（还没轮到） | $0 + 3 = 3$ | 选了 $1$ 件 |
| ③ | $dp[2]$ | $dp[0] = 0$ | 否（边界值） | $0 + 3 = 3$ | 选了 $1$ 件 |
$dp[j - 2]$ 读到的是上轮旧值（即 $dp[i-1][j-2]$），每一步的决策互不干扰，物品最多只被选了 $1$ 次。
5. 与「条形蛋糕」（P17012）的关联
六级真题「条形蛋糕」（P17012）的转移方程为：
\[dp[i] = \max_{1 \le j \le i}\{p_j + dp[i - j]\}\]如果我们把蛋糕总长度 $n$ 视为背包容量，长度为 $j$ 的蛋糕块视为一种物品（体积 $= j$，价值 $= p_j$），每种物品可以无限使用，那么条形蛋糕就是一个完全背包问题。两道题的代码结构几乎相同，理解了一道就能理解另一道。
6. 样例验证
以样例为例（$n = 3, V = 10$）：
| 物品编号 | 体积 $w$ | 价值 $val$ | 性价比 $val / w$ |
|---|---|---|---|
| $1$ | $2$ | $3$ | $1.50$ |
| $2$ | $3$ | $4$ | $1.33$ |
| $3$ | $4$ | $5$ | $1.25$ |
物品 $1$ 的性价比最高。选 $5$ 件物品 $1$：总体积 $= 5 \times 2 = 10$，总价值 $= 5 \times 3 = 15$。
DP 数组的完整更新过程（仅展示处理完所有物品后的最终结果）：
| $j$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $dp[j]$ | $0$ | $0$ | $3$ | $4$ | $6$ | $7$ | $9$ | $10$ | $12$ | $13$ | $15$ |
最终 $dp[10] = 15$，与样例输出一致。
注意：虽然本例中性价比最高的贪心策略恰好得到了正确答案，但贪心策略并非对所有背包问题都成立。动态规划才能保证找到全局最优解。
7. 复杂度分析
- 时间复杂度：$O(n \times V)$，外层循环 $n$ 种物品，内层循环容量 $V$
- 空间复杂度：$O(V)$，一维滚动数组
在本题数据范围下（$n, V \le 1000$），运算次数约为 $10^6$，远在时间限制内。
8. 注意事项
- $dp$ 数组初始化为全 $0$ 即可，因为我们求的是”不超过容量 $V$”的最大价值，空背包价值自然为 $0$
- 内层循环起点为 $w_i$（而非 $0$），因为容量小于 $w_i$ 时无法放入该物品，无需更新
- 最大总价值不会超过 $n \times \max(val_i) \times \lfloor V / \min(w_i) \rfloor$，在本题数据范围下
int类型足以存储
示例代码
通过一维 DP 数组正序遍历求解完全背包的最大价值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
// dp[j] 表示背包容量为 j 时能获得的最大总价值
int dp[1005];
int main() {
int n, V;
std::cin >> n >> V;
// 外层循环：枚举每一种物品
for (int i = 0; i < n; i++) {
int w, val;
std::cin >> w >> val;
// 内层循环：正序遍历容量（完全背包的关键）
// 从 w 开始，因为容量小于 w 时无法放入该物品
for (int j = w; j <= V; j++) {
// 状态转移：选或不选第 i 种物品（可以重复选）
// dp[j - w] 可能已经包含了本轮选过的物品 i，从而实现无限选取
if (dp[j - w] + val > dp[j]) {
dp[j] = dp[j - w] + val;
}
}
}
// dp[V] 即为背包容量为 V 时的最大总价值
std::cout << dp[V] << std::endl;
return 0;
}
二维数组解法（更直观）
上面的一维滚动数组写法虽然简洁高效，但对初学者来说不太容易理解”正序遍历为什么能实现重复选取”。下面给出二维数组的写法，用 $dp[i][j]$ 明确表示”前 $i$ 种物品、背包容量为 $j$ 时的最大总价值”，状态含义一目了然。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
// dp[i][j] 表示：前 i 种物品、背包容量为 j 时的最大总价值
int dp[1005][1005];
int w[1005], val[1005];
int main() {
int n, V;
std::cin >> n >> V;
for (int i = 1; i <= n; i++) {
std::cin >> w[i] >> val[i];
}
// 外层循环：枚举前 i 种物品
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
// 不选第 i 种物品：继承前 i-1 种物品的结果
dp[i][j] = dp[i - 1][j];
// 选（至少）一件第 i 种物品
// 注意这里是 dp[i][j - w[i]]，而不是 dp[i-1][j - w[i]]
// 用的是"本行"已更新的值，所以同一物品可以被反复选取
if (j >= w[i] && dp[i][j - w[i]] + val[i] > dp[i][j]) {
dp[i][j] = dp[i][j - w[i]] + val[i];
}
}
}
std::cout << dp[n][V] << std::endl;
return 0;
}
二维写法的核心理解点：转移时用的是 dp[i][j - w[i]]（本行已更新的值），而非 dp[i-1][j - w[i]]（上一行的旧值）。如果把 dp[i] 改成 dp[i-1]，就变成了 01 背包。通过下标就能直观看出两种背包的本质区别。
| 对比项 | 二维 $dp[i][j]$ | 一维 $dp[j]$（上文） |
|---|---|---|
| 状态含义 | 前 $i$ 种物品、容量 $j$ 的最大价值 | 容量 $j$ 的最大价值（滚动覆盖） |
| 空间复杂度 | $O(n \times V)$ | $O(V)$ |
| 可读性 | 更直观，两个维度含义清晰 | 需理解滚动数组的覆盖机制 |
| 核心区别 | 转移时用 $dp[i][j-w]$（本行）vs $dp[i-1][j]$（上一行） | 正序遍历自然实现”本行覆盖” |
小提示：二维写法空间开销较大（$O(n \times V)$），在本题数据范围下（$n, V \le 1000$）约需 $4$ MB，仍可通过。但在数据范围更大的题目中，建议使用一维滚动数组优化空间。
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
