前言分支限界法branch and bound是一种在解空间树上做系统性搜索、并用「界函数」剪掉不可能产生最优解的分支的算法框架。它和回溯法backtracking经常被放在一起讲但两者的搜索方式和目标并不相同回溯法通常用深度优先的方式枚举所有可行解靠约束函数剪枝分支限界法更强调「当前能得到的最好值」与「某个分支理论上能达到的最好值」的比较一旦后者不可能超过前者就整枝剪掉。常见的误解有三个。第一把分支限界法等同于贪心贪心只沿一条路走分支限界仍然会探索多条分支只是用界来淘汰。第二认为界函数越精确越好界越紧剪枝越强但计算界的开销也越大需要权衡。第三把「上界」和「下界」用反求最大化问题时界函数必须是该分支能达到的上界只有上界不超过当前最优解时才能安全剪枝用成下界会把最优解剪掉。本文以 0-1 背包为例讲清界函数的设计、优先队列式best-first分支限界的实现以及它和回溯式实现的差别。代码以 C17 为基准。一、解空间树与搜索策略0-1 背包问题有n件物品第i件重量w[i]、价值v[i]背包容量C。每件物品要么全拿要么不拿求不超过容量的最大总价值。它的解空间是一棵二叉树第i层对应第i件物品左分支表示「拿」右分支表示「不拿」。从根到叶的一条路径就是一个完整的取舍方案。朴素枚举有2^n个叶子分支限界要做的就是在到达叶子之前判断某些子树不可能产生更好的解从而跳过它们。常见的搜索顺序有三种策略数据结构特点深度优先栈 / 递归内存占用小容易实现接近回溯法广度优先队列按层扩展内存占用随层数增长最佳优先优先队列按界排序优先扩展最有希望的分支常能更快找到好解本文实现最佳优先版本每次从优先队列中取出界最大的结点扩展。这样更容易早早就得到一个接近最优的可行解从而用这个解去剪掉更多分支。二、界函数分数背包松弛对最大化问题界函数要回答从当前结点继续往下走最多还能得到多少价值一个经典的上界是把剩余物品按「单位重量价值」从高到低排序然后允许把物品切开分数背包。分数背包的最优值是 0-1 背包最优值的上界因为放宽了「只能整件拿」的约束。设当前结点已经决定了前level件物品已选总价值profit、总重量weight。界函数如下若weight C该分支已经装满界就是profit。否则按单位价值从高到低尽量把剩余物品整件装入累加价值和重量。遇到第一件装不下的物品时装入它的一个分数比例为(C - weight) / w[i]把v[i]乘以这个比例加入界。返回累加值。// 适用于 C17#include algorithm#include cstddef#include queue#include vectorstruct Item {int weight;int value;};struct Node {int level; // 已决定前 level 件物品int profit;int weight;double bound; // 该结点子树能达到的价值上界};double boundOf(const Node u, const std::vectorItem items, int capacity) {if (u.weight capacity) {return static_castdouble(u.profit);}double b static_castdouble(u.profit);int totalWeight u.weight;std::size_t i static_caststd::size_t(u.level);while (i items.size() totalWeight items[i].weight capacity) {totalWeight items[i].weight;b items[i].value;i;}if (i items.size()) {int remain capacity - totalWeight;b static_castdouble(remain) * items[i].value / items[i].weight;}return b;}这里有一个前提items必须已经按单位价值value / weight从大到小排序。否则第 2 步的贪心填充不是分数背包的最优解得到的值可能不是上界剪枝就会剪掉真正的最优解。排序时不能用浮点除法做比较否则可能因为精度问题违反严格弱序strict weak ordering而传给std::sort的比较器不满足严格弱序是未定义行为undefined behavior, UB。用交叉相乘// 适用于 C17std::sort(items.begin(), items.end(), [](const Item a, const Item b) {return static_castlong long(a.value) * b.weight static_castlong long(b.value) * a.weight;});交叉相乘的结果可能超出int所以先转long long。如果价值或重量本身接近10^9乘积会接近10^18仍在 64 位有符号整数的范围内再大就需要__int128或高精度而那已经超出本文的范围。三、最佳优先搜索的实现优先队列需要按bound从大到小出队。std::priority_queue默认是大顶堆但它用less比较的是整个元素我们只关心bound所以自定义比较器// 适用于 C17struct ByBound {bool operator()(const Node a, const Node b) const {return a.bound b.bound; // 注意方向a.bound 小则 a 优先级低}};std::priority_queueT, Container, Compare的Compare语义和std::sort相反Compare(a, b) true表示a排在b之后优先级更低。所以要让bound大的先出队比较器要写a.bound b.bound。// 适用于 C17int knapsack(std::vectorItem items, int capacity) {std::sort(items.begin(), items.end(), [](const Item a, const Item b) {return static_castlong long(a.value) * b.weight static_castlong long(b.value) * a.weight;});std::priority_queueNode, std::vectorNode, ByBound pq;Node root{0, 0, 0, 0.0};root.bound boundOf(root, items, capacity);pq.push(root);int best 0;while (!pq.empty()) {Node u pq.top();pq.pop();if (u.bound static_castdouble(best)) {continue; // 整棵子树不可能更好}if (u.level static_castint(items.size())) {best std::max(best, u.profit);continue;}const Item it items[static_caststd::size_t(u.level)];// 左分支拿这件物品if (u.weight it.weight capacity) {Node take{u.level 1, u.profit it.value,u.weight it.weight, 0.0};take.bound boundOf(take, items, capacity);if (take.bound static_castdouble(best)) {pq.push(take);}}// 右分支不拿Node skip{u.level 1, u.profit, u.weight, 0.0};skip.bound boundOf(skip, items, capacity);if (skip.bound static_castdouble(best)) {pq.push(skip);}}return best;}逐处说明best记录目前找到的完整可行解的最大价值。初始为 0对应「一件都不拿」。出队时如果u.bound best说明这棵子树里不可能有严格更好的解直接丢弃。用而不是是可以的值相等的解不需要再找。到达叶子level n时更新best。左分支只有在「拿了不超重」时才生成右分支总是能生成。生成子结点后先算界界不超过best就不入队减少队列长度。有一个边界需要特别注意boundOf在u.weight capacity时返回u.profit。如果写成返回 0那么一个刚好装满的结点入队时界是 0可能被best剪掉导致漏掉最优解。这是实现界函数时最容易犯的错误之一。四、和回溯式分支限界的对比同样的界函数也可以配深度优先搜索使用递归进入左分支、右分支进入前用bound best判断是否剪枝。这种写法不需要优先队列内存是 O(n) 的递归栈但可能很晚才找到好的可行解剪枝效果依赖遍历顺序。维度最佳优先优先队列深度优先递归数据结构std::priority_queue调用栈空间最坏 O(2^n) 个结点O(n)找到好解的速度通常较快取决于顺序实现复杂度需要定义结点和比较器简单适用场景解空间不太大、想要尽早剪枝内存受限、实现简单优先两种写法都依赖同一个界函数。分支限界的「限界」指的就是这个界而不是某种固定的剪枝规则界函数设计得好不好直接决定算法是「比暴力快一点」还是「实际可用」。五、一个可手工推演的例子三件物品(w, v) (10, 60)、(20, 100)、(30, 120)容量 50。单位价值分别是 6、5、4已经按降序排列。根结点界先装 10价值 60再装 20价值 160剩 20第三件装 2/3加 80界为 240。取第一件重量 10、价值 60剩余物品可装 20 20/30×120 80界 220。不取第一件可装 20 30 50价值 220界 220。继续展开可以枚举出最优解是「拿第 1、2 件」价值 160重量 30或者「拿第 2、3 件」价值 220重量 50。最优值是 220。分支限界会在界不超过 220 时剪掉其余分支。这个例子说明界函数只是上界真正的最优值要等搜索到叶子才能确认。常见坑点1. 界函数不是上界❌ 求最大值时用「剩余物品全部装入」的价值当界但没考虑容量界可能小于实际可达值。✅ 用分数背包松弛保证界不低于任何可行解并且验证bound 子树中任意可行解的 profit。2. 物品没有按单位价值排序❌ 直接按输入顺序做贪心填充得到的值不是分数背包最优解可能低于真实上界。✅ 先按value / weight降序排序再计算界。3. 排序比较器用浮点除法❌return (double)a.value / a.weight (double)b.value / b.weight;精度问题可能破坏严格弱序。✅ 用交叉相乘并转成long long防止溢出。4. 优先队列比较器方向写反❌return a.bound b.bound;以为大的先出队。✅std::priority_queue的Compare返回true表示优先级更低要写a.bound b.bound。5. 装满的结点界被算成 0❌boundOf里if (weight capacity) return 0;✅ 返回profit否则刚好装满的可行解会被错误剪掉。6. 剪枝条件用了严格小于❌ 只剪bound best大量等值分支继续扩展队列膨胀。✅ 用bound best值相等不可能产生更优解。7. 优先队列内存失控❌ 对n 50的背包直接跑最佳优先队列里可能堆积大量结点。✅ 评估解空间规模内存敏感时改用深度优先分支限界或加更紧的界。8. 用 int 累加价值和重量❌int在容量或价值较大时溢出属于有符号整数溢出UB。✅ 用long long存累加值界函数里先转double再乘比例。总结要点结论核心解空间树 界函数剪枝最大化问题的界必须是上界背包的界分数背包松弛搜索策略最佳优先、深度优先、广度优先时间复杂度最坏仍是指数级实际取决于剪枝空间复杂度最佳优先最坏 O(2^n)深度优先 O(n)关键细节排序、界的方向、装满结点的界分支限界法不是一种能保证多项式时间的「魔法」它只是把「枚举」变成了「有依据地不枚举」。界函数越紧、搜索顺序越合理被剪掉的分支越多但最坏情况下它仍然可能遍历整个解空间。写这类算法时先把界函数的正确性证清楚再谈优化否则很容易在某个边界上把最优解剪掉而且很难通过小数据发现。