完全背包 —— 题解

欢迎阅读 欢迎来到「完全背包」题解之旅本文将带你从最基础的背包问题出发深入理解完全背包与 01 背包的核心区别并掌握如何分别处理“至多装满”和“恰好装满”两种经典问法。在开始之前建议你先了解题目背景这是牛客网 DP42 模板题给定 nn 种物品每种物品无限件背包容量为 VV求能装入的最大价值同时额外要求恰好装满时的最大价值若无法装满则输出 0。本质上完全背包是 01 背包的延伸但遍历顺序截然不同。明确学习目标掌握完全背包的一维空间优化写法理解正序和逆序遍历的区别并熟练处理“恰好装满”时的初始化技巧。本文将从问题转化、状态定义、转移方程、初始化、填表顺序到代码实现层层递进。即使你对背包问题还不熟悉我们也会从 01 背包复习开始对比引入完全背包让你轻松抓住核心思想。现在让我们一起装满背包解开完全背包的奥秘吧 一、题目【模板】完全背包_牛客题霸_牛客网二、做题思路问题转化前置分析完全背包允许每种物品无限次选取与01背包的核心区别在于容量遍历方向。本题包含两个子问题不要求装满求容量不超过V时的最大价值。要求恰好装满求容量恰好等于V时的最大价值若不可达输出0。第一问不要求装满的最大价值1. 状态表示核心基础定义dp[i][j]表示从前i种物品中选取每种可重复选总体积不超过j时能获得的最大总价值。i范围0到nj范围0到V。该状态与完全背包标准定义一致。2. 状态转移方程关键难点暴力想法枚举选几个对于第i种物品体积v价值w假设选k个则dp[i][j] max( dp[i-1][j], // k0不拿 dp[i-1][j-v] w, // k1 dp[i-1][j-2v] 2w, // k2 dp[i-1][j-3v] 3w, // k3 ... )dp[i][j-v]的展开式现在我们写出dp[i][j-v]的展开式容量减少一个v但物品种类仍是前i种dp[i][j-v] max( dp[i-1][j-v], // k0不拿 dp[i-1][j-2v] w, // k1 dp[i-1][j-3v] 2w, // k2 dp[i-1][j-4v] 3w, // k3 ... )把dp[i][j-v]的每一项都加上w得到dp[i][j-v] w max( dp[i-1][j-v] w, // 即原式的第1项 dp[i-1][j-2v] 2w, // 即原式的第2项 dp[i-1][j-3v] 3w, // 即原式的第3项 ... )因此原式可以直接合并为dp[i][j] max( dp[i-1][j], dp[i][j-v] w )这个新式子不再需要枚举k因为dp[i][j-v]本身已经包含了选多个第i种物品的最优结果通过当前行左侧状态进行递推完美体现了“无限使用”的特性。3. 初始化边界防护前0种物品任意容量下最大价值均为0不选任何物品因此dp[0][j] 0默认全0初始化即可。4. 填表顺序递推方向dp[i][j]依赖上一行dp[i-1][j]和当前行左侧dp[i][j - v[i-1]]因此必须按行从上到下i从1到n列从左到右j从1到V遍历。正序容量保证dp[i][j - v[i-1]]已考虑过当前物品的多次选取实现无限次使用。5. 返回值目标映射直接输出dp[n][V]即所有物品、容量V下的最大价值。第二问恰好装满的最大价值1. 状态表示核心基础定义dp[i][j]表示从前i种物品中选取每种可重复选总体积恰好等于j时的最大总价值。若无法恰好装满则状态为不可达用-1标记。2. 状态转移方程关键难点同样两种决策不选继承dp[i-1][j]可能为-1。选至少一次前提是j v[i-1]且dp[i][j - v[i-1]] ! -1说明剩余容量可恰好装满价值为dp[i][j - v[i-1]] w[i-1]。3. 初始化边界防护dp[0][0] 0前0种物品容量0恰好装满价值为0空集。dp[0][j] -1j 0无物品可选时无法装满任何正容量标记为不可达。代码中通过循环for (int j1; jV; j) dp[0][j] -1;实现dp[0][0]保持0。4. 填表顺序递推方向与第一问相同按行从上到下列从左到右正序保证完全背包的重复选取特性。转移时依赖当前行左侧状态。5. 返回值目标映射若dp[n][V] -1表示无法恰好装满输出0否则输出dp[n][V]。三、代码#include iostream #include string.h using namespace std; const int N 1010; int n, V; // 物品种数背包容量 int v[N], w[N]; // 每种物品的体积和价值 int dp[N][N]; // dp[i][j]前 i 种物品容量 j 的最大价值 int main() { // 读入数据 cin n V; for (int i 0; i n; i) { cin v[i] w[i]; } // 第一问完全背包最大价值不要求恰好装满 // 1. 创建dp表默认初始化为0全局变量已清零 // 2. 初始化dp[0][j] 0表示前0种物品任何容量下价值为0 // 3. 填表顺序外层遍历物品种类内层遍历容量从小到大 // 因为完全背包允许重复选当前物品所以正序遍历容量 // 使得 dp[i][j - v[i-1]] 已经是考虑过当前物品后的状态实现重复选取。 for (int i 1; i n; i) { for (int j 1; j V; j) { // 4. 状态转移方程完全背包二维形式 // 不选第 i 种物品dp[i][j] dp[i-1][j] // 选第 i 种物品至少一次dp[i][j] max(dp[i][j], dp[i][j - v[i-1]] w[i-1]) // 注意这里使用 dp[i][j - v[i-1]] 而不是 dp[i-1][...]表示允许重复选取。 dp[i][j] dp[i - 1][j]; if (j v[i - 1]) { dp[i][j] max(dp[i][j], dp[i][j - v[i - 1]] w[i - 1]); } } } // 5. 输出不要求装满时的最大价值 cout dp[n][V] endl; // 第二问恰好装满时的最大价值完全背包 // 重置dp表 memset(dp, 0, sizeof(dp)); // 初始化只有容量0在“前0种物品”下恰好装满价值0其余容量不可达设为-1 for (int j 1; j V; j) { dp[0][j] -1; // 容量 j0 时前0种物品无法恰好装满置 -1 } // 填表顺序同上完全背包正序容量 for (int i 1; i n; i) { for (int j 1; j V; j) { // 不选当前物品继承上一行的状态可能为 -1 dp[i][j] dp[i - 1][j]; // 选当前物品重复选要求容量足够且当前行 dp[i][j - v[i-1]] 可达即 ! -1 // 因为完全背包允许重复所以用当前行状态 dp[i][...] 检查。 if (j v[i - 1] dp[i][j - v[i - 1]] ! -1) { dp[i][j] max(dp[i][j], dp[i][j - v[i - 1]] w[i - 1]); } } } // 输出若 dp[n][V] -1 表示无法恰好装满输出0否则输出最大价值 cout (dp[n][V] -1 ? 0 : dp[n][V]) endl; return 0; }四、流程图流程一不要求恰好装满的完全背包最大价值流程二恰好装满的完全背包最大价值五、优化状态转移方程对于第i种物品体积v[i-1]价值w[i-1]决策为选或不选但由于可重复选一维转移为dp[j] max(dp[j], dp[j - v[i-1]] w[i-1])当j v[i-1]时。等号右边的dp[j]为上一轮不选当前物品的值dp[j - v[i-1]]则是本轮已更新的值允许重复选取。填表顺序外层循环遍历每种物品i从1到n内层循环必须正序遍历容量j从1到V。为什么完全背包要正序因为完全背包允许无限次选取当前物品dp[j]需要利用同一物品已更新过的较小容量状态dp[j - v[i-1]]即表示“已经选过一次当前物品后继续选”的累计价值。若采用逆序如01背包dp[j - v[i-1]]仍为上一轮状态则每个物品最多被选一次无法实现重复选取。正序的具体作用当j从小到大遍历时dp[j - v[i-1]]已经在本轮被更新过因为j - v[i-1] j先被处理所以它包含了当前物品的多次选取信息从而允许无限取用。与01背包逆序的对比01背包中每个物品只能选一次必须保证dp[j - v[i-1]]是上一轮状态因此需要逆序遍历容量避免覆盖。#include iostream #include string.h using namespace std; const int N 1010; int n, V; int v[N], w[N]; int dp[N]; // 一维滚动数组dp[j] 表示当前容量 j 下的最大价值 int main() { cin n V; for (int i 0; i n; i) { cin v[i] w[i]; } // 第一问完全背包不要求装满 // dp 初始全0全局变量表示空背包价值为0 for (int i 1; i n; i) { // 完全背包正序遍历容量 j允许重复取当前物品 // 因为 dp[j - v[i-1]] 在本轮已经更新过可体现“无限取用” for (int j 1; j V; j) { if (j v[i - 1]) { dp[j] max(dp[j], dp[j - v[i - 1]] w[i - 1]); } } } cout dp[V] endl; // 第二问完全背包恰好装满 memset(dp, 0, sizeof(dp)); for (int j 1; j V; j) { dp[j] -1; // 其他容量初始为“不可达” } for (int i 1; i n; i) { // 同样正序允许重复取 for (int j 1; j V; j) { // 只有前一个状态可达! -1且容量够时才考虑选当前物品 if (j v[i - 1] dp[j - v[i - 1]] ! -1) { dp[j] max(dp[j], dp[j - v[i - 1]] w[i - 1]); } } } cout (dp[V] -1 ? 0 : dp[V]) endl; return 0; }时间复杂度O(n × V)与二维实现完全一致外层循环遍历 n 种物品内层循环正序遍历容量j从 1 到 V。每个状态同样只做常数次比较和更新因此总操作数仍为 n × V。由于完全背包要求正序容量内层无法提前退出必须遍历全部容量故时间上无优化空间。空间复杂度O(V)显著优于二维实现仅使用一维数组dp长度为 V1所有状态复用同一数组。完全背包正序更新时dp[j - v[i-1]]已被当前物品更新过天然实现“重复选取”效果无需保留上一层全部数据。第二问重置dp并初始化dp[1..V] -1空间仍为 O(V)。 闭幕 恭喜你完成了「完全背包」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题有两个问不要求装满和恰好装满。代码中第二问为什么要把dp[0] 0而其他dp[j] -1这样初始化代表什么含义完全背包的一维写法中容量j是从小到大枚举的。如果改成从大到小结果会变成什么背包问题其实就是01背包你可以试着用一个小例子如体积2价值3容量4推演一下两种顺序的区别。二维写法中选当前物品时用的是dp[i][j - v[i-1]]而不是dp[i-1][...]请你用自己的话解释一下为什么这样就能实现“重复取无限次”延伸挑战试着将本题的代码改成01背包每种物品只能选一次只需要改哪一处循环顺序动手改一改并验证结果是否正确。如果题目要求输出最大价值的同时还要输出有多少种不同的选法能达到这个最大值你该如何在 DP 中额外记录方案数尝试用完全背包的思路解决零钱兑换LeetCode 322给定硬币面值和总金额求凑成总金额所需的最少硬币个数看看状态转移和初始化与本题有何异同。如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在DP 的道路上越走越稳早日攻克每一道难题下次见 ✨