《牛客 01背包模板问题》

一、题目【模板】01背包_牛客题霸_牛客网二、做题思路2.1 状态表示核心基础本题包含两个子问题需分别定义状态方案一不要求装满dp1[i][j]表示从前i个物品中选取总体积不超过j时能获得的最大总价值。方案二要求恰好装满dp2[i][j]表示从前i个物品中选取总体积恰好等于j时能获得的最大总价值。若无法达到该体积则状态为不可达用-1标记。2.2 状态转移方程关键难点对于每件物品i我们面临选或不选两种决策不选第i件物品继承前i-1件物品的结果即dp[i][j] dp[i-1][j]。选第i件物品前提是当前容量j ≥ v[i]。此时将第i件放入背包价值增加w[i]剩余容量为j - v[i]需利用前i-1件物品在容量j - v[i]下的最优结果。方案一由于不要求装满任何容量j下只要不超过即可因此选择与否取较大值dp1[i][j] max(dp1[i-1][j], (j ≥ v[i] ? dp1[i-1][j - v[i]] w[i] : 0))若j v[i]则只能不选dp1[i][j] dp1[i-1][j]。方案二要求恰好装满必须保证选第i件后剩余容量j - v[i]恰好可由前i-1件装满即dp2[i-1][j - v[i]]必须可达不等于-1。转移为dp2[i][j] max(dp2[i-1][j], (j ≥ v[i] dp2[i-1][j - v[i]] ! -1) ? dp2[i-1][j - v[i]] w[i] : -1)若两者都不可行则dp2[i][j]保持-1。2.3 初始化边界防护方案一前0件物品任意容量下最大价值均为0因为不选任何物品体积不超过任何容量。因此dp1[0][j] 0默认全局0初始化即可无需额外赋值。方案二前0件物品只有容量0能被“恰好装满”空集其他容量j 0均无法装满标记为不可达-1。dp2[0][0] 0空集达到体积 0价值 0dp2[0][j] -1j 1..V表示无法恰好装满这些容量。此初始化必须显式执行代码中通过循环for (int j1; jV; j) dp2[0][j] -1;实现。2.4 填表顺序递推方向dp[i][j]依赖dp[i-1][j]上方和dp[i-1][j-v[i]]左上方因此从上到下i从 1 到n从左到右j从 1 到V遍历确保前置状态已就绪。2.5 返回值目标映射方案一直接输出dp1[n][V]即前n件物品、容量V下的最大价值。方案二若dp2[n][V] -1表示无法恰好装满输出0否则输出dp2[n][V]。三、代码#include vector #include string #include iostream using namespace std; const int N 1010; int n, V; // 物品数量背包容量 int v[N], w[N]; // 物品体积物品价值 int dp1[N][N]; // 第一问普通0/1背包dp1[i][j]表示前i个物品、容量j的最大价值 int dp2[N][N]; // 第二问恰好装满的0/1背包dp2[i][j]表示前i个物品、容量j恰好装满时的最大价值不可达为-1 int main() { cin n V; for (int i 1; i n; i) { cin v[i] w[i]; } // 第一问最大价值不必恰好装满 // 1. 创建dp表dp1[N][N]已全局定义并初始化为0 // 2. 初始化dp1[0][j] 0默认表示前0个物品任何容量下价值为0 // 3. 填表顺序从上到下i从1到n从左到右j从1到V // 因为dp1[i][j]依赖于dp1[i-1][j]和dp1[i-1][j-v[i]] for (int i 1; i n; i) { for (int j 1; j V; j) { // 4. 状态转移方程 // 不选第i个物品dp1[i][j] dp1[i-1][j] // 选第i个物品前提j v[i]dp1[i][j] max(当前, w[i] dp1[i-1][j-v[i]]) dp1[i][j] dp1[i - 1][j]; if (j v[i]) { dp1[i][j] max(dp1[i][j], w[i] dp1[i - 1][j - v[i]]); } } } // 5. 返回值输出dp1[n][V] 即为前n个物品、容量V下的最大价值不必装满 cout dp1[n][V] endl; // 第二问恰好装满时的最大价值 // 1. 创建dp表dp2[N][N]全局定义初始化为0 // 2. 初始化 // 第一行i0表示前0个物品只有容量0为“恰好装满”价值为0其他容量均不可达设为-1 for (int j 1; j V; j) { dp2[0][j] -1; // 不可达状态初始化 } // dp2[0][0] 默认为0表示容量0恰好装满可行 // 3. 填表顺序从上到下i从1到n从左到右j从1到V // 因为dp2[i][j]依赖于dp2[i-1][j]和dp2[i-1][j-v[i]] for (int i 1; i n; i) { for (int j 1; j V; j) { // 4. 状态转移方程 // 不选第i个物品继承上一行状态可能为-1表示不可达 dp2[i][j] dp2[i - 1][j]; // 选第i个物品要求容量足够且前一个状态必须可达即前 i-1 个物品能恰好装满 j - v[i] if (j v[i] dp2[i - 1][j - v[i]] ! -1) { dp2[i][j] max(dp2[i][j], w[i] dp2[i - 1][j - v[i]]); } } } // 5. 返回值输出若dp2[n][V] -1表示无法恰好装满则输出0根据题意否则输出最大价值 cout (dp2[n][V] -1 ? 0 : dp2[n][V]) endl; return 0; }四、流程图五、优化使用滑动数组状态转移方程关键难点对于每件物品i我们只在一维数组上原地更新方案一选或不选取较大值dp1[j] max(dp1[j], dp1[j - v[i]] w[i])当j v[i]时。其中等号右边的dp1[j]等价于二维的dp1[i-1][j]dp1[j - v[i]]等价于dp1[i-1][j - v[i]]。方案二必须保证dp2[j - v[i]]可达不为-1才能转移dp2[j] max(dp2[j], dp2[j - v[i]] w[i])当j v[i]且dp2[j - v[i]] ! -1时。填表顺序递推方向关键点一维数组必须采用逆序遍历j从V到v[i]。因为dp[j]的更新依赖dp[j - v[i]]若从小到大遍历dp[j - v[i]]可能已经在当前物品的处理中被更新过导致物品被重复选取违背 01 背包每个物品只能选一次。逆序遍历保证dp[j - v[i]]仍为上一轮前i-1件物品的状态与二维的dp[i-1][j-v[i]]等价。#include vector #include string #include iostream using namespace std; const int N 1010; int n, V; // 物品数量背包容量 int v[N], w[N]; // 物品体积物品价值 int dp1[N]; // 第一问普通0/1背包dp1[j]表示容量j能获得的最大价值 int dp2[N]; // 第二问恰好装满dp2[j]表示容量j恰好装满时的最大价值不可达为-1 int main() { cin n V; for (int i 1; i n; i) { cin v[i] w[i]; } // 第一问最大价值不必恰好装满 // 1. 创建dp表一维数组dp1初始全为0全局变量默认0 // 2. 初始化dp1[j]0表示任何容量下不选任何物品价值为0 // 3. 填表顺序外层遍历物品i1..n内层容量j从V递减到v[i] // 倒序保证每个物品只选一次0/1背包特性 for (int i 1; i n; i) { for (int j V; j v[i]; j--) { // 4. 状态转移方程 // 不选当前物品dp1[j]保持不变 // 选当前物品dp1[j] max(dp1[j], w[i] dp1[j - v[i]]) // 由于一维数组max操作自动保留了“不选”和“选”的较大值 dp1[j] max(dp1[j], w[i] dp1[j - v[i]]); } } // 5. 返回值输出dp1[V] 即为前n个物品、容量V下的最大价值不必装满 cout dp1[V] endl; // 第二问恰好装满时的最大价值 // 1. 创建dp表一维数组dp2 // 2. 初始化 // dp2[0] 0 表示容量0恰好装满空背包价值为0 // dp2[j] -1 表示容量jj1目前不可达无法恰好装满 for (int j 1; j V; j) { dp2[j] -1; } // dp2[0] 默认0全局变量无需赋值 // 3. 填表顺序外层遍历物品i1..n内层容量j从V递减到v[i]仍为0/1背包倒序 for (int i 1; i n; i) { for (int j V; j v[i]; j--) { // 4. 状态转移方程 // 选当前物品时前提是容量足够且前一个状态 dp2[j - v[i]] 必须可达不等于-1 // 因为要保证“恰好装满”只有从可达状态转移过来新的状态才是可达的 // 不可达状态-1不参与转移避免错误累加 if (dp2[j - v[i]] ! -1) { dp2[j] max(dp2[j], w[i] dp2[j - v[i]]); } // 不选当前物品dp2[j] 不变可能是-1或已存在的价值 } } // 5. 返回值输出若 dp2[V] -1 表示容量V无法恰好装满根据题意输出0 // 否则输出恰好装满时的最大价值 cout (dp2[V] -1 ? 0 : dp2[V]) endl; return 0; }