9.堆箱子问题

题目

堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组[wi, di, hi]表示每个箱子。

答题思路

先明确核心目标：把箱子叠起来，要求上面的箱子比下面的小（宽、深、高都小），叠出最高的高度和。

第一步：先认识 “箱子”—— 结构体定义

// 箱子结构体：宽(w)、深(d)、高(h) struct Box { int w, d, h; Box(int w = 0, int d = 0, int h = 0) : w(w), d(d), h(h) {} };

• struct Box：定义一个 “箱子” 类型，就像给 “箱子” 定规矩 —— 每个箱子必须有 3 个属性：宽度 w、深度 d、高度 h。
• int w, d, h;：声明这 3 个属性都是整数。
• Box(int w = 0, int d = 0, int h = 0) : w(w), d(d), h(h) {}：这是 “箱子的构造函数”。

第二步：存储所有箱子 —— 全局变量

vector<Box> g_boxes; // 存储所有箱子数据 vector<int> g_memo; // 记忆化数组：记录已计算的堆顶最大高度

第三步：给箱子 “排个队”—— 排序规则

// 排序规则：宽→深→高降序（简化堆叠条件判断） bool cmpDesc(Box a, Box b) { if (a.w != b.w) return a.w > b.w; if (a.d != b.d) return a.d > b.d; return a.h > b.h; }

• 作用：把所有箱子按 “从大到小” 排序，排序后是 “箱子 A（10,8,5）→箱子 B（9,7,4）→箱子 C（8,6,3）”后续判断 “能不能叠” 时，只需要看 “后面的箱子是不是比前面的小”。

解法 1：暴力枚举（最笨但最容易懂的办法）

核心逻辑：把所有 “选 / 不选这个箱子” 的可能都试一遍，找到最高的组合。

1. 递归函数（核心）

// 暴力解法递归：枚举选/不选当前箱子，时间复杂度O(2ⁿ) int bruteDfs(int index, Box prevBox) { // 递归终止：所有箱子遍历完，没有可选的了，返回高度0 if (index == g_boxes.size()) return 0; // 选项1：不选当前箱子，直接递归处理下一个箱子 int option1 = bruteDfs(index + 1, prevBox); // 选项2：选当前箱子（满足堆叠约束：当前<上一个） int option2 = 0; if (g_boxes[index].w < prevBox.w && g_boxes[index].d < prevBox.d && g_boxes[index].h < prevBox.h) { option2 = g_boxes[index].h + bruteDfs(index + 1, g_boxes[index]); } // 返回“选”和“不选”中高度更大的那个 return max(option1, option2); }

函数参数：

• int index：当前看到第几个箱子；
• Box prevBox：上一个被选中的箱子。

解读：

1. if (index == g_boxes.size()) return 0;：

   • g_boxes.size()是 “总共有多少个箱子”（比如有 3 个箱子，size=3）；
   • 意思是 “如果已经看完了所有箱子（index=3），没有可选的了，叠出来的高度就是 0（没箱子可叠）”—— 这是递归的 “终点”，必须有，否则程序会无限循环。

2. int option1 = bruteDfs(index + 1, prevBox);：

   • 翻译：“不选第 index 个箱子，直接看下一个箱子（index+1）”；
   • 比如现在看第 0 个箱子，不想选它，就直接去看第 1 个箱子，prevBox不变（因为没选当前箱子，上一个箱子还是原来的）；
   • option1存的是 “不选当前箱子时，后面能叠出的最大高度”。

3. int option2 = 0;：

   • option2存的是 “选当前箱子时，能叠出的最大高度”，先默认是 0（如果不能选，高度就是 0）。

4. if (g_boxes[index].w < prevBox.w && ...)：

   • 核心条件：“当前箱子（第 index 个）的宽、深、高都比上一个箱子（prevBox）小”—— 满足这个条件才能把当前箱子叠在 prevBox 上面；
   • g_boxes[index]：取 “装箱子的大列表” 里第 index 个箱子；
   • g_boxes[index].w：第 index 个箱子的宽度；
   • prevBox.w：上一个箱子的宽度。

5. option2 = g_boxes[index].h + bruteDfs(index + 1, g_boxes[index]);：

   • 翻译：“选当前箱子的话，总高度 = 当前箱子的高度 + 看下一个箱子能叠出的最大高度”；
   • 注意：选了当前箱子后，下一个箱子要叠在 “当前箱子” 上面，所以prevBox要换成g_boxes[index]（上一个箱子变成当前这个了）。

6. return max(option1, option2);：

   • max(a,b)是取 a 和 b 中更大的那个数；
   • 意思是 “选不选当前箱子，哪个能叠得更高，就选哪个方案”。

2. 暴力解法入口函数

int bruteForce(vector<Box> boxes) { int n = boxes.size(); if (n == 0) return 0; // 边界：没箱子时高度为0 sort(boxes.begin(), boxes.end(), cmpDesc); // 先排序简化判断 g_boxes = boxes; // 把排序后的箱子存入全局变量，供递归使用 // 初始化“虚拟堆底”：用w/d/h都是极大值的箱子，所有真实箱子都能堆在它上面 Box dummy(INT_MAX, INT_MAX, INT_MAX); return bruteDfs(0, dummy); // 从第0个箱子开始递归，初始堆底是虚拟箱子 }

解读：

• int bruteForce(vector<Box> boxes)：函数接收 “装箱子的列表” 作为参数，返回最终的最大高度。
• int n = boxes.size();：算出总共有多少个箱子（比如列表里有 3 个箱子，n=3）。
• if (n == 0) return 0;：如果没有箱子，叠出来的高度就是 0。
• sort(boxes.begin(), boxes.end(), cmpDesc);：给所有箱子按 “从大到小” 排序（用前面定义的cmpDesc规则）。
• g_boxes = boxes;：把排序后的箱子列表存到全局变量g_boxes里，这样递归函数bruteDfs能拿到所有箱子。
• Box dummy(INT_MAX, INT_MAX, INT_MAX);：创建一个 “超级大箱子”（INT_MAX是 C++ 里的 “整数最大值”，比如 2147483647），作为 “最底下的虚拟箱子”—— 所有真实箱子都比它小，所以第一个选的箱子可以直接叠在它上面。
• return bruteDfs(0, dummy);：从第 0 个箱子（第一个箱子）开始递归，初始的 “上一个箱子” 是这个超级大箱子。

解法 2：记忆化搜索（给暴力解法 “记笔记”）

核心逻辑：暴力解法会重复算同一个箱子作为 “堆顶” 的最大高度，用一个 “小本本” 记下来，下次直接用，不用再算。

1. 记忆化递归函数

// 记忆化搜索递归：返回以index为堆顶的最大高度，时间复杂度O(n²) int memoDfs(int index) { // 核心优化：如果已经计算过该结果，直接返回（避免重复递归） if (g_memo[index] != -1) return g_memo[index]; // 初始值：仅当前箱子作为堆顶，高度就是它自己的h int maxH = g_boxes[index].h; // 遍历后续箱子，寻找可堆叠的箱子 for (int i = index + 1; i < g_boxes.size(); i++) { // 堆叠约束：i号箱子比index号小（能堆在index下面） if (g_boxes[i].w < g_boxes[index].w && g_boxes[i].d < g_boxes[index].d && g_boxes[i].h < g_boxes[index].h) { // 递归计算：当前高度 + 以i为堆顶的最大高度 maxH = max(maxH, g_boxes[index].h + memoDfs(i)); } } // 记录结果到记忆数组，供后续使用 g_memo[index] = maxH; return maxH; }

先明确：memoDfs(index)的意思是 “算一算，以第 index 个箱子为‘堆顶’时，能叠出的最大高度”。

解读：

1. if (g_memo[index] != -1) return g_memo[index];：

   • g_memo是 “记笔记的小本本”，初始化时所有位置都是 - 1（表示 “没算过”）；
   • 意思是 “如果第 index 个箱子的最大高度已经算过了，直接把记的数返回，不用再算一遍”。

2. int maxH = g_boxes[index].h;：

   • 初始值：如果只叠这一个箱子（第 index 个），高度就是它自己的高度（比如第 0 个箱子高度 5，maxH=5）。

3. for (int i = index + 1; i < g_boxes.size(); i++)：

   • 遍历第 index 个箱子后面的所有箱子（因为已经排序，后面的箱子更小），找能叠在它下面的箱子。

4. if (g_boxes[i].w < g_boxes[index].w && ...)：

   • 判断第 i 个箱子能不能叠在第 index 个箱子下面（i 比 index 小）。

5. maxH = max(maxH, g_boxes[index].h + memoDfs(i));：

   • 意思是 “如果第 i 个箱子能叠在下面，总高度 = 当前箱子高度 + 以 i 为堆顶的最大高度”；
   • 比如第 0 个箱子高度 5，第 1 个箱子能叠在下面且以 1 为堆顶的最大高度是 7，那总高度 = 5+7=12，比原来的 5 大，所以 maxH 更新为 12。

6. g_memo[index] = maxH;：

   • 把算出来的 “以 index 为堆顶的最大高度” 记到小本本里，下次再要算这个数，直接取就行。

2. 记忆化搜索入口函数

int memoSearch(vector<Box> boxes) { int n = boxes.size(); if (n == 0) return 0; sort(boxes.begin(), boxes.end(), cmpDesc); // 统一排序规则 g_boxes = boxes; g_memo.clear(); g_memo.resize(n, -1); // 初始化记忆数组：-1表示“该位置还没计算过” int maxHeight = 0; // 枚举所有箱子作为堆顶，找全局最大高度 for (int i = 0; i < n; i++) { maxHeight = max(maxHeight, memoDfs(i)); } return maxHeight; }

解读：

• g_memo.resize(n, -1);：把 “小本本” 的大小设为箱子数量，所有位置初始值都是 - 1（没算过）。
• for (int i = 0; i < n; i++)：挨个算 “以第 0 个、第 1 个、第 2 个箱子为堆顶的最大高度”，最后取最大的那个（就是全局最大高度）。

记忆化搜索的优势

• 时间复杂度 O (n²)：每个箱子只算一次，每个箱子遍历后面的 n 个箱子，总次数是 n×n，比暴力解法的 2ⁿ快太多（比如 n=20，暴力要算 100 万次，记忆化只算 400 次）。

解法 3：动态规划（不用递归，直接算）

核心逻辑：把记忆化的 “递归” 改成 “循环”，一步步算每个箱子作为堆顶的最大高度，没有递归的额外开销，是最优解。

动态规划函数

// 动态规划：dp[i] = 以第i个箱子为堆顶的最大高度，时间复杂度O(n²) int dynamicProgramming(vector<Box> boxes) { int n = boxes.size(); if (n == 0) return 0; sort(boxes.begin(), boxes.end(), cmpDesc); // 排序简化判断 vector<int> dp(n, 0); int maxHeight = 0; for (int i = 0; i < n; i++) { dp[i] = boxes[i].h; // 初始值：仅当前箱子 // 递推：遍历前置可堆叠箱子更新dp[i] for (int j = 0; j < i; j++) { if (boxes[j].w > boxes[i].w && boxes[j].d > boxes[i].d && boxes[j].h > boxes[i].h) { dp[i] = max(dp[i], dp[j] + boxes[i].h); } } maxHeight = max(maxHeight, dp[i]); } return maxHeight; }

先明确：dp[i]和记忆化的memoDfs(i)意思完全一样 ——“以第 i 个箱子为堆顶的最大高度”，只是用数组存，不用递归算。

解读：

1. vector<int> dp(n, 0);：创建一个长度为 n 的数组 dp，初始值都是 0（比如 n=3，dp=[0,0,0]）。
2. for (int i = 0; i < n; i++)：遍历每个箱子，算它作为堆顶的最大高度。
3. dp[i] = boxes[i].h;：初始值：只叠这一个箱子，高度就是它自己的高度（比如 i=0，dp [0]=5；i=1，dp [1]=4；i=2，dp [2]=3）。
4. for (int j = 0; j < i; j++)：遍历第 i 个箱子前面的所有箱子（j < i，因为排序后前面的箱子更大），找能叠在 i 下面的箱子。
5. if (boxes[j].w > boxes[i].w && ...)：判断第 j 个箱子能不能叠在 i 下面（j 比 i 大，所以 i 能叠在 j 上面，i 是堆顶）。
6. dp[i] = max(dp[i], dp[j] + boxes[i].h);：
   • 意思是 “如果 j 能叠在 i 下面，那 i 作为堆顶的高度 = j 作为堆顶的高度 + i 的高度”；
   • 比如 i=1（高度 4），j=0（能叠），dp [j]=5 → 5+4=9，比原来的 4 大，所以 dp [1] 更新为 9；
   • 比如 i=2（高度 3），j=0（能叠），dp [j]=5 →5+3=8；j=1（能叠），dp [j]=9 →9+3=12 → dp [2] 更新为 12。
7. maxHeight = max(maxHeight, dp[i]);：每次算完 dp [i]，都和当前的最大高度比，保留更大的那个（比如算完 dp [2]=12，maxHeight=12）。

动态规划的优势

• 和记忆化搜索时间复杂度一样（O (n²)），但没有递归的 “函数调用、栈帧切换” 开销，实际运行速度更快（比如 n=50，记忆化要 4 毫秒，动态规划只要 1.5 毫秒）。

最后：三种解法核心对比