前言
分支限界法（branch and bound）是一种在解空间树上做系统性搜索、并用「界函数」剪掉不可能产生最优解的分支的算法框架。它和回溯法（backtracking）经常被放在一起讲，但两者的搜索方式和目标并不相同：回溯法通常用深度优先的方式枚举所有可行解，靠约束函数剪枝；分支限界法更强调「当前能得到的最好值」与「某个分支理论上能达到的最好值」的比较，一旦后者不可能超过前者，就整枝剪掉。
常见的误解有三个。第一，把分支限界法等同于贪心：贪心只沿一条路走，分支限界仍然会探索多条分支，只是用界来淘汰。第二，认为界函数越精确越好：界越紧剪枝越强，但计算界的开销也越大，需要权衡。第三，把「上界」和「下界」用反：求最大化问题时，界函数必须是该分支能达到的上界，只有上界不超过当前最优解时才能安全剪枝；用成下界会把最优解剪掉。
本文以 0-1 背包为例，讲清界函数的设计、优先队列式（best-first）分支限界的实现，以及它和回溯式实现的差别。代码以 C++17 为基准。
一、解空间树与搜索策略
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]乘以这个比例加入界。 - 返回累加值。
// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <queue>
#include <vector>
struct Item {
int weight;
int value;
};
struct Node {
int level; // 已决定前 level 件物品
int profit;
int weight;
double bound; // 该结点子树能达到的价值上界
};
double boundOf(const Node& u, const std::vector<Item>& items, int capacity) {
if (u.weight >= capacity) {
return static_cast<double>(u.profit);
}
double b = static_cast<double>(u.profit);
int totalWeight = u.weight;
std::size_t i = static_cast<std::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_cast<double>(remain) * items[i].value / items[i].weight;
}
return b;
}这里有一个前提：items必须已经按单位价值value / weight从大到小排序。否则第 2 步的贪心填充不是分数背包的最优解，得到的值可能不是上界，剪枝就会剪掉真正的最优解。
排序时不能用浮点除法做比较，否则可能因为精度问题违反严格弱序（strict weak ordering），而传给std::sort的比较器不满足严格弱序是未定义行为（undefined behavior, UB）。用交叉相乘：
// 适用于 C++17
std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
return static_cast<long long>(a.value) * b.weight >
static_cast<long long>(b.value) * a.weight;
});交叉相乘的结果可能超出int，所以先转long long。如果价值或重量本身接近10^9，乘积会接近10^18，仍在 64 位有符号整数的范围内；再大就需要__int128或高精度，而那已经超出本文的范围。
三、最佳优先搜索的实现
优先队列需要按bound从大到小出队。std::priority_queue默认是大顶堆，但它用less比较的是整个元素；我们只关心bound，所以自定义比较器：
// 适用于 C++17
struct ByBound {
bool operator()(const Node& a, const Node& b) const {
return a.bound < b.bound; // 注意方向：a.bound 小则 a 优先级低
}
};std::priority_queue<T, Container, Compare>的Compare语义和std::sort相反：Compare(a, b) == true表示a排在b之后（优先级更低）。所以要让bound大的先出队，比较器要写a.bound < b.bound。
// 适用于 C++17
int knapsack(std::vector<Item> items, int capacity) {
std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
return static_cast<long long>(a.value) * b.weight >
static_cast<long long>(b.value) * a.weight;
});
std::priority_queue<Node, std::vector<Node>, 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_cast<double>(best)) {
continue; // 整棵子树不可能更好
}
if (u.level == static_cast<int>(items.size())) {
best = std::max(best, u.profit);
continue;
}
const Item& it = items[static_cast<std::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_cast<double>(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_cast<double>(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) |
| 关键细节 | 排序、界的方向、装满结点的界 |
分支限界法不是一种能保证多项式时间的「魔法」，它只是把「枚举」变成了「有依据地不枚举」。界函数越紧、搜索顺序越合理，被剪掉的分支越多；但最坏情况下它仍然可能遍历整个解空间。写这类算法时，先把界函数的正确性证清楚，再谈优化，否则很容易在某个边界上把最优解剪掉，而且很难通过小数据发现。
