如何用自顶向下法获取无界背包选中物品及限高3D盒子堆叠利润最大化问题

首先得回忆下无界背包的自顶向下DP逻辑：我们通常用递归加记忆化的方式，定义dp[i][w]表示考虑前i种物品、背包容量为w时能拿到的最大价值。状态转移时，对于第i个物品，要么不选它（此时dp[i][w] = dp[i-1][w]），要么选它（此时dp[i][w] = dp[i][w - weight[i]] + value[i]，前提是w >= weight[i]，因为无界背包允许重复选同一种物品）。

要回溯找出选中的物品，咱们可以从最终状态dp[n][W]（n是物品总数，W是背包总容量）倒推：

• 从第n种物品开始往回遍历到第1种：
  • 如果dp[i][w] == dp[i-1][w]，说明没选第i种物品，直接跳到第i-1种继续检查；
  • 如果dp[i][w] == dp[i][w - weight[i]] + value[i]，说明选了第i种物品，把它记下来，然后将w减去该物品的重量weight[i]，继续检查第i种物品（因为可以重复选）；
• 重复这个过程，直到w变成0或者遍历完所有物品。

举个小例子帮你理解：假设物品重量是[2,3]，价值是[3,4]，背包容量5。最终dp[2][5] = 7（选1个重量2的物品和1个重量3的物品）。回溯步骤：

1. 从dp[2][5]开始，dp[1][5] = 6（选两个重量2的物品），和7不相等，说明选了第2种物品，w变成5-3=2；
2. 现在看dp[2][2]，它等于dp[1][2] = 3，说明没选第2种物品，跳到第1种；
3. dp[1][2]等于dp[1][0] + 3（dp[1][0]是0），说明选了第1种物品，w变成0，结束。
   最终选中的就是第2种和第1种物品。

这个问题看起来有点复杂，但咱们拆解一下就清晰了：核心是处理盒子的旋转，再转化为带约束的堆叠优化问题。

第一步：处理盒子的旋转 #

每个3D盒子有3个维度，我们可以把它旋转成最多3种有效堆叠状态——因为堆叠只要求下层底面的长和宽分别≥上层的，所以我们可以把每个状态的底面长和宽按长≥宽排序，这样后续判断堆叠条件会更简单。

比如原始盒子的维度是h1, h2, h3，先把三个维度排序为a ≥ b ≥ c，然后生成三种有效状态：

• 底面为(a,b)，高度为c，利润不变；
• 底面为(a,c)，高度为b，利润不变；
• 底面为(b,c)，高度为a，利润不变。

这样每个原始盒子就变成了3个候选盒子，接下来问题就转化为：从这些候选盒子里选一个堆叠序列，满足上层盒子的底面长和宽都≤下层的，总高度不超过H，总利润最大。

第二步：排序候选盒子 #

把所有候选盒子按底面长降序排序，如果长相同，就按底面宽降序排序。这样排序后，我们只需要保证堆叠序列的宽也是非递增的（因为长已经降序了），就能满足堆叠的底面约束。

第三步：动态规划求解 #

这里可以用类似最长上升子序列（LIS）的DP思路，结合高度约束：

• 定义dp[j]表示以第j个候选盒子为顶部的堆叠，总高度不超过H时的最大利润。初始时，dp[j]就是该盒子自身的利润（只要它的高度≤H）；
• 对于每个盒子j，遍历所有i < j的盒子（因为已经按长降序，所以i的长肯定≥j的长），如果i的宽≥j的宽，且i堆叠的总高度 + j的高度 ≤ H，那么就可以更新dp[j] = max(dp[j], dp[i] + j的利润)；
• 最终的答案就是所有dp[j]中的最大值（前提是对应的总高度≤H）。

如果候选盒子数量不多（比如n≤100，那3n=300，O((3n)^2)=90000次操作完全没问题），这种方法足够高效。如果n很大，可以用线段树或单调队列优化查询过程，不过一般题目里用基础方法就够了。

第四步：回溯找堆叠序列 #

找到最大利润后，咱们可以从对应的盒子j倒推：

• 找所有i < j满足i的长≥j的长、i的宽≥j的宽，且dp[j] == dp[i] + j的利润、i的总高度 + j的高度 ≤ H；
• 记录下j，然后继续以i为起点倒推，直到找不到符合条件的i；
• 最后把记录的盒子反转，就是从下到上的堆叠顺序。

举个简单例子：原始盒子是(3,2,1,10)（长、宽、高、利润），H=5。生成的候选盒子是：

1. (3,2,1,10)（底面3×2，高度1）
2. (3,1,2,10)（底面3×1，高度2）
3. (2,1,3,10)（底面2×1，高度3）

排序后顺序不变。处理过程：

• dp[0] = 10（单独放第一个盒子，高度1≤5）；
• dp[1] = max(10, dp[0]+10=20)（把第二个盒子放在第一个上面，总高度1+2=3≤5）；
• dp[2] = max(10, dp[0]+10=20, dp[1]+10=30)（把第三个盒子放在第二个上面，总高度2+3=5≤5）；
  最终最大利润是30，对应的堆叠是第三个盒子放在第二个盒子上面。

内容的提问来源于stack exchange，提问作者user2134