动态规划实战从装箱问题看01背包的优化技巧附洛谷P1049题解很多算法爱好者和信息学竞赛选手在初次接触动态规划时都会觉得它既强大又有些“玄学”。尤其是经典的01背包问题它不仅是理解动态规划思想的绝佳入口更是后续解决更复杂问题如分组背包、树形DP的基石。但很多人在掌握了基础的二维DP解法后就止步不前了殊不知从二维到一维的优化不仅仅是代码行数的减少更是对状态转移本质理解的深化。今天我们就以洛谷上经典的P1049装箱问题为战场深入剖析01背包的优化技巧看看如何将看似简单的思路打磨成高效、优雅的代码。对于参加NOIP、CSP等竞赛的选手来说装箱问题这类题目几乎是必考题。它考察的不仅仅是你能不能写出一个正确的程序更在于你能否在有限的时间和内存限制下写出最优化的解。我见过不少选手在本地测试时程序运行无误一到线上评测就超时或内存超限问题往往就出在没有进行必要的优化上。这篇文章我们就来彻底解决这个问题。1. 问题本质为什么装箱问题就是01背包装箱问题的描述很简单有一个容量为V的箱子和N个物品每个物品有一个体积。要求选择一些物品装入箱子使得箱子的剩余空间最小。换句话说就是让装入物品的总体积尽可能大但不能超过箱子容量。注意这里最容易陷入的误区是尝试用贪心算法。比如“每次选最大的能放进去的物品”或者“每次选最小的物品”通过简单的反例如容量为4物品体积为3,2,2就能证明贪心会得到错误答案。动态规划是解决此类“选择”问题的标准武器。如果我们换个角度看“剩余空间最小”等价于“已使用空间最大”。而“已使用空间”不能超过总容量V。这立刻让我们联想到01背包的经典设问在总容量限制下如何选择物品使得总价值最大在装箱问题中每个物品的“价值”就是它的“体积”。我们追求的就是在不超过背包容量的前提下装入物品的总体积最大值。设这个最大值为max_used那么答案就是V - max_used。所以装箱问题可以毫无障碍地转化为01背包问题。理解这一点是我们所有后续讨论的起点。下面的表格清晰地展示了这种转化关系概念经典01背包问题装箱问题 (P1049)背包容量总承重W箱子总容量V物品第i个物品第i个物品物品属性1重量weight[i]体积a[i]物品属性2价值value[i]价值 体积a[i]目标最大化总价值∑value最大化总体积∑a[i](即总“价值”)最终答案最大总价值dp[n][W]最小剩余空间V - dp[n][V]2. 从直觉到方程二维DP的建立与实现我们先从最符合直觉的二维动态规划开始。定义状态是DP的核心。对于“前i个物品”和“当前可用容量j”这类选择问题一个非常通用的状态定义是dp[i][j]考虑前i个物品在总容量限制为j的情况下所能获得的最大价值在本题中是最大总体积。这个定义几乎可以套用到所有01背包及其变种问题上。状态定义好后我们需要考虑状态如何转移也就是如何从已知的小问题答案推导出大问题的答案。对于第i个物品我们只有两种选择不选它那么情况就退化到只考虑前i-1个物品容量仍为j。此时的最大价值就是dp[i-1][j]。选它前提是这个物品的体积a[i]不能超过当前容量j。如果选了它我们会消耗掉a[i]的容量剩下的j - a[i]容量用来装前i-1个物品。此时的总价值是dp[i-1][j - a[i]] a[i]物品i的价值a[i]加上之前部分的最大价值。我们的目标是最大化总价值所以状态转移方程就是在这两种选择中取最大值if (j a[i]) { dp[i][j] max(dp[i-1][j], dp[i-1][j - a[i]] a[i]); } else { dp[i][j] dp[i-1][j]; // 容量不够只能不选 }初始条件也很直观当没有物品可选时i0无论容量多大最大价值都是0。当容量为0时无论有多少物品最大价值也是0。for (int j 0; j V; j) dp[0][j] 0; for (int i 0; i n; i) dp[i][0] 0;基于这个思路我们可以写出洛谷P1049的二维DP解法代码。代码结构清晰非常适合理解动态规划的整个过程#include iostream #include algorithm using namespace std; int main() { int V, n; cin V n; int a[35]; // 物品体积题目约定n30稍微开大一点 for (int i 1; i n; i) { cin a[i]; } // dp[i][j]: 前i个物品容量j下的最大总体积 int dp[35][20005] {0}; // 容量V20000 // 动态规划过程 for (int i 1; i n; i) { for (int j 1; j V; j) { if (j a[i]) { dp[i][j] max(dp[i-1][j], dp[i-1][j - a[i]] a[i]); } else { dp[i][j] dp[i-1][j]; } } } // 答案是总容量减去能装的最大体积 cout V - dp[n][V] endl; return 0; }这段代码的时间复杂度是O(n * V)空间复杂度也是O(n * V)。对于本题的数据范围n30, V20000二维数组大小约为 30 * 20000 * 4字节 ≈ 2.4MB完全在限制内。运行时间也足够。那么为什么我们还要优化呢3. 空间优化的艺术一维滚动数组详解在竞赛中题目对内存的限制往往比较严格。虽然本题用二维数组没问题但很多变种问题的容量V或物品数n可能很大导致二维数组开不下。更重要的是从二维优化到一维是理解DP状态依赖关系的关键一步这种思想会贯穿整个动态规划的学习。观察上面的状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j - a[i]] a[i])你会发现在计算第i层的状态dp[i][j]时它只依赖于第i-1层的两个状态正上方的dp[i-1][j]和左前方的dp[i-1][j - a[i]]。它完全不依赖同一层i层的其他状态也不依赖更早的层。这意味着我们并不需要保存整个二维表格。在计算完第i层后第i-1层的数据除了用来计算第i层就没有其他用处了。那么我们是否可以只用一个一维数组在不断更新的过程中让它始终表示“当前考虑完前i个物品后”的状态呢我们尝试定义一维数组f[j]希望它在第i轮循环结束后表示考虑完前i个物品、容量为j时的最大价值。如果我们直接从左到右遍历j会出现问题假设我们正在计算第i轮f[j]目前还保存着第i-1轮的结果即dp[i-1][j]。当我们计算新的f[j]时需要用到旧的f[j](即dp[i-1][j]) 和旧的f[j - a[i]]。但是如果j从小到大遍历在计算f[j]时f[j - a[i]]可能已经被本轮的更新覆盖了它不再是dp[i-1][j - a[i]]而是变成了dp[i][j - a[i]]。这违背了状态转移的依赖关系。解决这个问题的钥匙是逆序枚举容量j。我们从j V开始倒着计算到j a[i]。这样当我们计算f[j]时f[j - a[i]]由于下标更小还没有被本轮更新过它保存的依然是上一轮i-1轮的结果dp[i-1][j - a[i]]完全符合我们的要求。更新公式变为for (int j V; j a[i]; j--) { f[j] max(f[j], f[j - a[i]] a[i]); }对于j a[i]的情况物品i根本放不下状态保持不变即f[j]继承上一轮的值我们在逆序循环中直接从j V到j a[i]自然跳过了这些j。这个过程就像是一个“滚动”的数组不断用新的状态覆盖旧的状态。初始化时f[0]0表示容量为0时最大价值为0其他f[j]也初始化为0表示在考虑0个物品时任何容量下的最大价值都是0。让我们用表格来模拟一下一维数组的更新过程假设箱子容量V10物品体积为[4, 5, 6]。初始状态 (考虑0个物品):j012345678910f[j]00000000000加入第1个物品 (体积4):逆序更新 j10 down to 4j10:f[10] max(f[10], f[6]4) max(0, 04)4j9:f[9] max(f[9], f[5]4) max(0, 04)4...j4:f[4] max(f[4], f[0]4) max(0, 04)4j4 不更新此时状态 (考虑完第1个物品):j012345678910f[j]00004444444加入第2个物品 (体积5):逆序更新 j10 down to 5j10:f[10] max(f[10], f[5]5) max(4, 45)9j9:f[9] max(f[9], f[4]5) max(4, 45)9j8:f[8] max(f[8], f[3]5) max(4, 05)5j7:f[7] max(f[7], f[2]5) max(4, 05)5j6:f[6] max(f[6], f[1]5) max(4, 05)5j5:f[5] max(f[5], f[0]5) max(4, 05)5此时状态 (考虑完前2个物品):j012345678910f[j]00004555599可以看到f[10]9对应选择了物品1(4)和物品2(5)。整个更新过程中我们只使用了一个一维数组就完成了所有计算。最终的优化代码如下#include iostream #include algorithm using namespace std; int main() { int V, n; cin V n; int a[35]; for (int i 1; i n; i) cin a[i]; int f[20005] {0}; // 一维DP数组初始化为0 for (int i 1; i n; i) { // 关键容量j必须逆序遍历 for (int j V; j a[i]; j--) { f[j] max(f[j], f[j - a[i]] a[i]); } } cout V - f[V] endl; return 0; }空间复杂度从 O(n*V) 骤降到 O(V)。这是一个质的飞跃。4. 边界处理与代码细节写出健壮的AC代码理论理解了但在实际编码提交时很多选手会因为一些细节问题丢分。下面我们针对洛谷P1049讨论几个关键的实现细节。1. 数组大小题目明确给出 V 20000, n 30。所以物品体积数组a开[35]足够。一维DP数组f开[20005]即可通常习惯开得比最大值稍大一点比如5。如果使用二维DP数组应开dp[35][20005]。2. 输入与初始化输入顺序是先V后n不要弄反。一维数组的初始化非常简单直接int f[20005] {0};即可确保所有元素为0。这是C的语法特性。如果使用vector可以用vectorint f(V1, 0);。3. 循环范围物品下标从1开始到n这样更直观与状态定义中的“前i个物品”对应。一维DP的内层循环for (int j V; j a[i]; j--)。注意条件是j a[i]当j a[i]时物品放不下状态保持原样无需操作。4. 输出答案答案是最小剩余空间即V - f[V]。f[V]就是考虑所有物品后容量为V时能装的最大体积。这里有一个我踩过的坑在极少数情况下如果题目输入的V就是0我们的循环for (int j V; j a[i]; j--)可能一次都不会执行因为V0肯定小于任何正的a[i]。但即使这样f[0]初始化为0也是正确的最终输出0 - f[0] 0答案正确。这说明我们的算法是健壮的。为了更清晰我将完整的、带有一维优化的AC代码再呈现一次并加上简要注释#include bits/stdc.h // 竞赛常用头文件包含大部分标准库 using namespace std; int main() { int V, n; cin V n; int items[35]; // 存储物品体积 for (int i 1; i n; i) { cin items[i]; } int dp[20005] {0}; // 一维DP数组dp[j]表示容量j下的最大体积 // 核心一维01背包模板 for (int i 1; i n; i) { // 逆序更新至关重要 for (int j V; j items[i]; --j) { // 状态转移不选 vs 选体积即价值 if (dp[j - items[i]] items[i] dp[j]) { dp[j] dp[j - items[i]] items[i]; } // 上面if语句等价于 dp[j] max(dp[j], dp[j-items[i]]items[i]); } } // 输出最小剩余空间 cout V - dp[V] endl; return 0; }这段代码非常简洁是01背包问题的标准模板。记住这个模板很多类似问题都可以套用。5. 举一反三01背包变种与练习建议掌握了装箱问题的解法你实际上已经掌握了01背包的核心。但在实际竞赛中问题不会这么直接。下面我列举几个常见的变种并给出如何用我们刚学到的知识去应对恰好装满要求背包必须恰好装满求最大价值或判断是否可能。解法是初始化时令dp[0]0其他dp[j]-INF负无穷大。这样只有能恰好凑出容量j的状态才是有效的正值。方案计数求恰好装满背包的方案数。将状态转移中的max改为求和初始化dp[0]1, 其余为0。二维费用每个物品有体积和重量两种消耗。状态需要升到二维dp[v][m]转移时需要同时满足两种容量限制。物品分组每组内的物品互斥最多选一个。这就是分组背包问题外层循环遍历组内层循环逆序遍历容量最内层循环遍历组内物品选哪个。对于想巩固01背包的选手我建议按以下顺序在洛谷或类似OJ上刷题P1048 采药最经典的01背包入门题价值与重量不同。P1060 开心的金明简单的01背包价值是价格与重要度的乘积。P1164 小A点菜求恰好花完钱的点菜方案数方案计数变种。P1507 NASA的食物计划二维费用背包问题。P1757 通天之分组背包标准的分组背包。在练习时务必自己动手实现一维优化版本。可以先用二维DP通过再改成一维DP对比两者的异同。遇到问题时在纸上画一画状态转移表模拟一下数据流动往往能很快找到症结所在。动态规划的学习没有捷径核心就是“状态定义”和“状态转移”。装箱问题作为一个完美的起点其优化过程中蕴含的“空间覆盖”和“逆序更新”思想会反复出现在后续更复杂的动态规划问题中。把这些基础打牢未来面对树形DP、状压DP时你才会更有底气。