动态规划解决堆箱子问题：从原理到代码实现
动态规划解决堆箱子问题：从原理到代码实现
在算法领域中，堆箱子问题是经典的动态规划应用场景之一。它不仅考察对问题的建模能力，更能深入体现动态规划“分解子问题、存储中间状态、复用最优解”的核心思想。本文将从问题定义出发，逐步推导动态规划解决方案，最终实现代码并探讨优化方向，适合算法初学者或需要巩固动态规划知识点的开发者阅读。
一、问题定义：什么是堆箱子问题？
堆箱子问题的经典描述为：给定一组长方体箱子，每个箱子都有三个维度（长、宽、高），我们需要将这些箱子堆叠起来，且满足以下两个条件：
上方箱子的长、宽必须严格小于下方箱子的长、宽（确保箱子能稳定放置，不考虑旋转箱子的情况）；
堆叠的目标是使总高度最大。
举个简单例子：若有两个箱子，箱子A（2,3,4）、箱子B（1,2,3），则B可以放在A上方，总高度为4+3=7，这是最优解。若存在箱子C（3,4,5），则最优堆叠为C→A→B，总高度5+4+3=12。
注意：本文暂不考虑箱子旋转的场景（即不允许将箱子的长、宽、高重新排列），后续优化部分会简要提及旋转场景的处理思路。
二、动态规划思路推导：如何建模子问题？
动态规划的核心是找到“最优子结构”和“重叠子问题”，堆箱子问题恰好满足这两个特性。我们逐步拆解思路：
2.1 排序：简化子问题的前提
由于箱子堆叠要求“上方严格小于下方”，我们可以先对所有箱子按某个维度（如长度）进行降序排序。排序后，对于第i个箱子，所有可能放在它下方的箱子都只能是前i-1个箱子（因为前i-1个箱子的长度≥第i个箱子的长度），这就将“全局寻找可堆叠箱子”转化为“局部寻找可堆叠箱子”，简化了子问题的范围。
排序规则：按长度降序排列，若长度相同则按宽度降序排列（进一步缩小后续判断范围）。
2.2 定义状态：存储中间最优解
定义dp[i]表示“以第i个箱子为最顶层箱子时，堆叠的最大高度”。这个状态定义的关键在于“以第i个箱子为顶”，确保了每个子问题的独立性，且最终的最优解就是dp数组中的最大值（因为最优堆叠的顶层必然是某个箱子）。
2.3 状态转移方程：推导最优解关系
对于第i个箱子，我们需要遍历前i-1个箱子（已排序），判断每个箱子j是否能放在第i个箱子的下方（即j的长>i的长且j的宽>i的宽）。若能放置，则以i为顶的最大高度可以更新为“dp[j] + 第i个箱子的高度”（即把i放在j的堆叠之上）；若不能放置，则以i为顶的高度就是其自身高度（仅放一个箱子i）。
用公式表示为：
$$dp[i] = height[i] + \max\left\{ dp[j] \mid j < i \text{ 且 } len[j] > len[i] \text{ 且 } wid[j] > wid[i] \right\}$$
若不存在满足条件的j，则dp[i] = height[i]。
2.4 初始化与结果计算
初始化：每个dp[i]的初始值为第i个箱子的高度（因为至少可以单独放置这个箱子）。
结果：遍历dp数组，最大值即为堆箱子的最大高度。
三、代码实现：C++实战
基于上述思路，我们用C++实现堆箱子问题的动态规划解法。代码中使用vector存储箱子数据，自定义排序规则实现降序排序，核心逻辑与前文思路完全一致，包含详细注释便于理解。
四、优化方向与拓展思考
4.1 允许箱子旋转的场景
实际问题中可能允许箱子旋转（即每个箱子的长、宽、高可以重新排列，但需保持长方体形态）。此时的处理思路是：为每个箱子生成所有可能的“非重复”旋转组合（如(2,3,4)可旋转为(3,2,4)、(4,2,3)等，但需去重），然后将这些组合加入箱子列表，再执行上述动态规划流程。
注意：旋转时需固定一个维度为“高”，避免重复计算（如将(2,3,4)视为“长2宽3高4”和“长3宽2高4”是不同的放置方式，但需根据问题要求判断是否需要区分）。
4.2 时间复杂度优化
上述基础解法的时间复杂度为O(n²)（排序O(nlogn) + 双重循环O(n²)），对于n较小的场景（如n≤1000）完全适用。若n较大（如n≥10000），可通过“排序+二分查找”优化为O(nlogn)：
排序后，按宽度维护一个“高度递增”的列表；
对于每个箱子，通过二分查找找到宽度小于当前箱子宽度的最大高度，进而更新dp值。
五、总结
堆箱子问题的动态规划解法核心在于“排序简化子问题范围+状态定义存储中间最优解+状态转移复用前序结果”。通过本文的分析，我们可以发现：动态规划的关键不是死记硬背公式，而是学会“拆解问题”——将复杂的堆叠问题拆解为“以每个箱子为顶的子问题”，再通过状态转移将子问题的解关联起来。
建议读者结合代码自行调试测试用例，尝试修改为“允许旋转”的版本，进一步加深对动态规划思想的理解。如果有疑问或优化建议，欢迎在评论区交流！