盒子堆叠问题的 4 种解法全解析：从贪心到回溯，从暴力到优化

在算法领域中，“盒子堆叠问题” 是经典的动态规划与贪心策略结合的案例，核心目标是将若干个长方体盒子堆叠起来，要求 “上面盒子的长、宽、高均严格小于下面的盒子”，最终得到最大堆叠高度（或对应的堆叠序列）。

本文将系统梳理盒子堆叠问题的 4 种解法，从基础的贪心、动态规划，到优化的二分查找方案，再到暴力回溯，覆盖不同场景下的选择逻辑。

一、问题定义

给定n个盒子，每个盒子有三个维度：width（宽）、depth（深）、height（高）。要求堆叠盒子时，任意上方盒子的宽、深、高必须严格小于下方盒子，求能得到的最大堆叠高度，以及对应的堆叠序列。

二、解法 1：贪心算法（局部最优，高效但非全局最优）

贪心是最直观的解法，核心思路是 “先选大盒子，再叠小盒子”。

实现步骤

1. 排序预处理：将盒子按 “宽度降序、深度降序、高度降序” 排序（保证优先选大盒子）；
2. 逐个堆叠：遍历排序后的盒子，只要当前盒子能放在栈顶盒子上方（满足尺寸约束），就将其加入堆叠序列。

代码示例

cpp

运行

#include <vector> #include <algorithm> #include <utility> using namespace std; struct Box { int width, depth, height; }; // 贪心排序规则：宽降序，宽相同则深降序，深相同则高降序 bool compareGreedy(const Box& a, const Box& b) { if (a.width != b.width) return a.width > b.width; if (a.depth != b.depth) return a.depth > b.depth; return a.height > b.height; } // 贪心解法：返回{总高度, 堆叠序列} pair<int, vector<Box>> greedySolution(vector<Box> boxes) { if (boxes.empty()) return {0, {}}; sort(boxes.begin(), boxes.end(), compareGreedy); vector<Box> stack; int totalH = 0; for (const auto& box : boxes) { if (stack.empty()) { stack.push_back(box); totalH += box.height; } else { const Box& top = stack.back(); if (box.width < top.width && box.depth < top.depth && box.height < top.height) { stack.push_back(box); totalH += box.height; } } } return {totalH, stack}; }

优缺点

• 优点：时间复杂度 O (nlogn)（仅排序开销），实现简单；
• 缺点：无法保证全局最优（可能错过 “先小盒子、后叠更多盒子” 的更优解）。

三、解法 2：动态规划（DP，全局最优，中等复杂度）

动态规划是解决 “盒子堆叠” 的标准解法，通过记录 “以第 i 个盒子为底的最大高度”，实现全局最优。

实现步骤

1. 排序预处理：同贪心（宽降序，保证后续只能选更小的盒子）；
2. 定义 DP 数组：dp[i]表示 “以第 i 个盒子为底时的最大堆叠高度”；
3. 状态转移：对于每个盒子i，遍历所有j < i的盒子，若j能放在i上方，则dp[i] = max(dp[i], dp[j] + boxes[i].height)；
4. 回溯序列：通过prev数组记录每个盒子的前驱，最终回溯得到堆叠序列。

代码示例

cpp

运行

pair<int, vector<Box>> dpSolution(vector<Box> boxes) { if (boxes.empty()) return {0, {}}; // 1. 排序 sort(boxes.begin(), boxes.end(), [](const Box& a, const Box& b) { if (a.width != b.width) return a.width > b.width; return a.depth > b.depth; }); int n = boxes.size(); vector<int> dp(n, 0); // dp[i]：以i为底的最大高度 vector<int> prev(n, -1); // 记录前驱，用于回溯序列 // 2. 初始化：每个盒子单独放的高度 for (int i = 0; i < n; i++) dp[i] = boxes[i].height; // 3. 状态转移 for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (boxes[j].width < boxes[i].width && boxes[j].depth < boxes[i].depth && boxes[j].height < boxes[i].height) { if (dp[j] + boxes[i].height > dp[i]) { dp[i] = dp[j] + boxes[i].height; prev[i] = j; } } } } // 4. 找最大高度对应的索引 int maxH = 0, maxIdx = 0; for (int i = 0; i < n; i++) { if (dp[i] > maxH) { maxH = dp[i]; maxIdx = i; } } // 5. 回溯得到堆叠序列 vector<Box> stack; while (maxIdx != -1) { stack.push_back(boxes[maxIdx]); maxIdx = prev[maxIdx]; } reverse(stack.begin(), stack.end()); // 反转后得到“从下到上”的序列 return {maxH, stack}; }

优缺点

• 优点：保证全局最优，逻辑通用；
• 缺点：时间复杂度 O (n²)，当 n 较大（如 n>1e4）时效率不足。

四、解法 3：DP + 二分查找（全局最优，O (nlogn) 高效）

通过将问题转化为最长递增子序列（LIS），结合二分查找，可将时间复杂度优化到 O (nlogn)。

核心思路

排序后，盒子的宽度已经降序，因此只需保证 “深度和高度递增” 即可满足堆叠约束 —— 这等价于在 “深度 + 高度” 数组中找最长递增子序列，而 LIS 可以用二分查找优化到 O (nlogn)。

代码示例

cpp

运行

pair<int, vector<Box>> dpBinarySearchSolution(vector<Box> boxes) { if (boxes.empty()) return {0, {}}; // 排序：宽降序，宽相同则深降序 sort(boxes.begin(), boxes.end(), [](const Box& a, const Box& b) { if (a.width != b.width) return a.width > b.width; return a.depth > b.depth; }); int n = boxes.size(); vector<int> tails; // tails[i]：长度为i+1的序列的最小末尾深度 vector<int> dp(n, 0); // dp[i]：以i为结尾的最大高度 vector<int> prev(n, -1); // 前驱索引 for (int i = 0; i < n; i++) { // 二分查找当前盒子能插入的位置 int left = 0, right = tails.size(); while (left < right) { int mid = (left + right) / 2; if (boxes[tails[mid]].depth > boxes[i].depth && boxes[tails[mid]].height > boxes[i].height) { right = mid; } else { left = mid + 1; } } // 更新tails和dp if (left == tails.size()) { tails.push_back(i); } else { tails[left] = i; } dp[i] = boxes[i].height; if (left > 0) { dp[i] += dp[tails[left-1]]; prev[i] = tails[left-1]; } } // 找最大高度对应的索引 int maxH = 0, maxIdx = 0; for (int i = 0; i < n; i++) { if (dp[i] > maxH) { maxH = dp[i]; maxIdx = i; } } // 回溯序列 vector<Box> stack; while (maxIdx != -1) { stack.push_back(boxes[maxIdx]); maxIdx = prev[maxIdx]; } reverse(stack.begin(), stack.end()); return {maxH, stack}; }

优缺点

• 优点：全局最优，时间复杂度 O (nlogn)，适合大规模数据；
• 缺点：实现较复杂，依赖排序后的维度约束。

五、解法 4：回溯法（暴力枚举，仅适用于小规模数据）

回溯法通过枚举所有可能的堆叠组合，找到满足约束的最大高度，但时间复杂度极高。

核心思路

递归枚举每个盒子 “选或不选”，选则判断是否能放在当前栈顶上方，最终记录所有合法组合中的最大高度。

代码示例（简化版）

cpp

运行

void backtrack(const vector<Box>& boxes, int idx, vector<Box>& curStack, int& maxH, vector<Box>& bestStack) { // 更新最大高度 int curH = 0; for (const auto& b : curStack) curH += b.height; if (curH > maxH) { maxH = curH; bestStack = curStack; } // 枚举后续盒子 for (int i = idx; i < boxes.size(); i++) { if (curStack.empty() || (boxes[i].width < curStack.back().width && boxes[i].depth < curStack.back().depth && boxes[i].height < curStack.back().height)) { curStack.push_back(boxes[i]); backtrack(boxes, i+1, curStack, maxH, bestStack); curStack.pop_back(); // 回溯 } } } pair<int, vector<Box>> backtrackSolution(vector<Box> boxes) { if (boxes.empty()) return {0, {}}; sort(boxes.begin(), boxes.end(), compareGreedy); // 先排序减少分支 vector<Box> curStack, bestStack; int maxH = 0; backtrack(boxes, 0, curStack, maxH, bestStack); return {maxH, bestStack}; }

优缺点

• 优点：逻辑简单，能枚举所有可能解；
• 缺点：时间复杂度 O (n!)，仅适用于 n≤10 的小规模场景。

六、解法对比与选择建议