P1855 榨取kkksc03 题解复盘模块动态规划目标在金钱和时间都有限的情况下最多完成多少个愿望基本信息项目内容题目编号、来源P1855 洛谷 / 榨取kkksc03训练层级B 变形题知识版块二维费用背包、01背包、动态规划解题前 · 关键信号识别维度分析目标、约束、底层结构目标在总金钱不超过M、总时间不超过T的情况下尽可能完成更多愿望。约束每个愿望只能完成一次。底层结构每个物品有两个费用限制金钱、时间属于二维费用 01 背包。数据规模n≤100M,T≤200使用O(nMT)可以通过。候选算法和依据算法二维费用 01 背包。依据每个愿望只能选择一次同时消耗两种资源因此需要用二维状态记录金钱和时间。复杂度预判时间复杂度O(n×M×T)空间复杂度O(M×T)。解题后 · 外化复盘维度内容实现结构 / 核心思路定义dp[j][k]表示使用不超过j元钱和k分钟时间时最多可以完成的愿望数。枚举每个愿望再分别倒序枚举金钱和时间使用dp[j][k]max(dp[j][k],dp[j-m][k-t]1)更新答案。错因回溯1. 容易把二维费用背包误写成一维背包只记录一种资源。2. 容易把金钱或时间正序枚举导致同一个愿望在同一轮被重复选择。3. 输入愿望数量时应枚举n不能误写成M或T。边界和易错点1. 每个愿望只能完成一次因此两个容量都必须倒序枚举。2.dp初始值默认为 0 即可因为什么都不选时完成愿望数为 0。3. 最终答案是dp[M][T]。下次看到什么信号我应该想到这个方法看到“每件物品只能选一次 有两个容量限制 求最大价值/最多数量”想到二维费用 01 背包。AC 完整代码#includeiostream#includequeue#includealgorithm#includevector#includeiomanipusingnamespacestd;structnode{intm,t;};intdp[205][205];intmain(){intn,M,T;cinnMT;node v[105];for(inti1;in;i){cinv[i].mv[i].t;}for(inti1;in;i){for(intjM;jv[i].m;j--){for(intkT;kv[i].t;k--){dp[j][k]max(dp[j][k],dp[j-v[i].m][k-v[i].t]1);}}}coutdp[M][T];return0;}本题知识点总结1. 状态定义dp[j][k]表示在金钱不超过j、时间不超过k的情况下最多可以完成多少个愿望。普通 01 背包只有一个容量dp[j]这题有两个限制金钱 时间所以状态增加一维dp[j][k]2. 状态转移对于当前愿望需要金钱m 需要时间t如果选择它dp[j-m][k-t]1如果不选择dp[j][k]因此dp[j][k]max(dp[j][k],dp[j-m][k-t]1);3. 为什么两个容量都倒序因为每个愿望只能完成一次。如果金钱或时间正序枚举本轮刚刚更新出的状态可能继续参与后面的转移相当于同一个愿望被重复使用。因此必须for(intjM;jm;j--){for(intkT;kt;k--){...}}4. 与普通01背包对比普通 01 背包一个容量限制状态dp[j]转移dp[j]max(dp[j],dp[j-w]v);二维费用背包两个容量限制状态dp[j][k]转移dp[j][k]max(dp[j][k],dp[j-w1][k-w2]value);5. 为什么这题价值是 1因为每完成一个愿望答案增加一个。所以dp[j-v[i].m][k-v[i].t]1这里的1就是再完成当前这个愿望。如果题目改成每个愿望还有一个价值w[i]那就会变成dp[j][k]max(dp[j][k],dp[j-m][k-t]w[i]);模型对比模型资源限制每件物品次数状态01背包1种一次dp[j]完全背包1种无限次dp[j]二维费用01背包2种一次dp[j][k]一句话总结看到“两个容量限制 每件物品只能选一次”想到二维费用 01 背包定义dp[j][k]两个容量全部倒序枚举。P1507 NASA的食物计划 题解复盘模块动态规划目标在体积和质量都有限的情况下选择若干食品使总卡路里最大基本信息项目内容题目编号、来源P1507 洛谷 / NASA的食物计划训练层级B 变形题知识版块二维费用背包、01背包、动态规划解题前 · 关键信号识别维度分析目标、约束、底层结构目标在总体积不超过H、总质量不超过T的情况下使所选食品的总卡路里最大。约束每个食品只能选择一次。底层结构每件物品同时消耗体积和质量两种资源因此属于二维费用 01 背包。数据规模H,T≤400n≤50使用O(nHT)可以通过。候选算法和依据算法二维费用 01 背包。依据每件食品只能选择一次并且有体积、质量两个容量限制。复杂度预判时间复杂度O(n×H×T)空间复杂度O(H×T)。解题后 · 外化复盘维度内容实现结构 / 核心思路定义dp[j][k]表示在体积不超过j、质量不超过k的情况下能够获得的最大卡路里。枚举每件食品再倒序枚举体积和质量使用dp[j][k]max(dp[j][k],dp[j-h][k-t]x)更新答案。错因回溯1. 容易把二维费用背包写成普通一维 01 背包漏掉质量或体积其中一个限制。2. 如果体积或质量正序枚举会导致同一件食品在同一轮被重复选择。3. 容易把第三个属性卡路里误当成容量而实际上它是价值。边界和易错点1. 每件食品只能使用一次因此两个容量都必须倒序。2.dp初始值为 0 即可因为可以什么都不选。3. 最终答案是dp[H][T]。下次看到什么信号我应该想到这个方法看到“每件物品只能选一次 有两个容量限制 求最大价值”想到二维费用 01 背包。AC 完整代码#includeiostream#includequeue#includealgorithm#includevector#includeiomanipusingnamespacestd;structnode{inth,t,x;};intdp[405][405];intmain(){intH,T,n;cinHTn;node v[55];for(inti1;in;i){cinv[i].hv[i].tv[i].x;}for(inti1;in;i){for(intjH;jv[i].h;j--){for(intkT;kv[i].t;k--){dp[j][k]max(dp[j][k],dp[j-v[i].h][k-v[i].t]v[i].x);}}}coutdp[H][T];return0;}本题知识点总结1. 状态定义dp[j][k]表示在体积不超过j、质量不超过k的情况下能够获得的最大总卡路里。这里j对应体积k对应质量。2. 状态转移当前食品体积 h 质量 t 卡路里 x如果不选dp[j][k]如果选择dp[j-h][k-t]x所以dp[j][k]max(dp[j][k],dp[j-h][k-t]x);3. 为什么两个容量都倒序因为每件食品只能选一次。如果正序for(intjh;jH;j)当前食品刚更新出来的状态可能继续参与本轮后面的转移相当于同一件食品被使用了多次。因此必须for(intjH;jh;j--){for(intkT;kt;k--){...}}4. 与普通01背包对比普通 01 背包一个容量限制状态dp[j]转移dp[j]max(dp[j],dp[j-w]v);NASA 食物计划两个容量限制状态dp[j][k]转移dp[j][k]max(dp[j][k],dp[j-h][k-t]x);5. 与 P1855 榨取kkksc03 对比题目两个容量价值P1855 榨取kkksc03金钱 时间每完成一个愿望1P1507 NASA的食物计划体积 质量每件食品有自己的卡路里x两题本质完全一样二维费用 01 背包只是价值不同。模型对比模型资源限制每件物品次数状态转移01背包1种一次dp[j]max(dp[j],dp[j-w]v)完全背包1种无限次dp[j]容量正序二维费用01背包2种一次dp[j][k]两个容量都倒序一句话总结看到“两个容量限制 每件物品只能选一次 求最大价值”想到二维费用 01 背包定义dp[j][k]两个容量全部倒序枚举。