企业官网建设流程全解析

“分支界定法”这个名字，我最早是在算法课的参考书上翻到的，当时只觉得它是“比回溯法多了一把剪刀”的搜索套路。真正让我对它刮目相看的，是几年前接手的一个库存拣选调度模块——场景可以简化成：一堆订单，每个订单占一定体积、产生一定收益，但配送车的载重和车厢空间都有限，怎么在几分钟内选出能让这次出库收益最大、又能塞进车里的订单组合。订单数不多，二十几个，但直接枚举组合就是 (2^{27}) 种，跑都跑不完。后来我把分支定界法（Branch and Bound）和 01 背包问题 的模型一套上去，配合一个优先队列实现的限界搜索，问题在毫秒级就稳定解完。这篇文章就把这套完整思路、C++ 代码和调试中踩过的坑全部摊开来讲，适合正在学算法、准备面试笔试的人，也适合项目里需要做组合优化但又不想上重量级求解器的同学参考。

1. 为什么是分支定界法：一个调度项目的真实痛点

先聊聊为什么我会从一堆精确解法里选中它。做组合优化的人，第一反应往往是动态规划（DP），尤其是 01 背包，动态规划几乎成了标准答案。但当时我遇到的实际约束里，除了总重量还有体积上限，某些订单之间还有“只能选其一”的互斥关系，DP 的状态维度一下子就膨胀成了三维、四维，状态转移方程写得人头疼。更麻烦的是，当背包容量达到十万、百万级别，DP 的二维表直接撑爆内存，根本没法上生产环境。

回溯法是另一个选项，思路简单，从第一个物品开始挨个试选或不选，走到叶子节点就记录一次结果。可它的问题在于“太老实”：就算明知道当前路径已经不可能超过历史最优了，它还继续一头扎进去搜到底。举个最直观的例子，背包容量 10，当前已经带了 9 重量的东西，价值累计 24，后面还剩一个重量 5 的物品，哪怕它的单件价值再高，回溯法也依然会尝试“选它”，直到在叶子层发现超重才回头。这种无效分支在物品数量多的时候会指数级扩散，程序很快就卡死。

分支定界法的核心区别，是它在搜索过程中始终维护一个“上界”的估计值。每个节点在被展开之前，我先算一算：就算后面的物品按最理想的情况全部塞进去，理论上最多还能拿多少价值。如果这个上界都低于当前已经找到的最优解，那这个节点下面的一切分支都不可能有更优结果，直接剪掉。翻译成人话就是：我已经知道这条路走到黑也超不过前面的记录了，干脆整条路不看。这个剪枝动作，让分支定界的实际搜索节点数往往比回溯法少几个数量级。

三种解法放在一起对比，选型逻辑就很清晰了。

当时我把这三个方案挨个试了一圈，动态规划在百万级容量面前直接内存爆掉，回溯法在 27 个订单面前跑到超时，只有分支定界法把搜索树剪得只剩一小簇，单次求解稳定在几百毫秒以内。从那以后，遇到类似的资源分配问题，我都优先考虑分支定界，这也是今天这篇文章的出发点。

1.1 分支定界法的核心思想：剪掉“不可能超过最优解”的分支

分支定界名字里两个关键词，一个是“分支”，一个是“定界”。

分支，是指把一个大问题不断拆分成互斥的子问题。对应到背包问题，就是每次面对一个物品，只做两种决定：选，或者不选。这个决定会生成两个新的子问题，每个子问题再继续对下一个物品做同样的事情，最终形成一棵二叉树，叶子节点就对应一个完整的选品方案。理论上这棵树的叶子有 (2^n) 个，分支定界不会全部遍历。

定界，是指给每个子问题快速估算一个“潜力上限”。这里的“上界”不是随便猜的，它必须保证：任何从这个节点往下扩展出来的可行方案，其真实价值都不会超过这个上界。如果某个节点的上界已经小于等于当前找到的最优解，那这个节点就可以被整棵剪掉。上界算得越紧，剪枝效果越好，但上界计算本身也要花时间，需要折中。

我给一个直觉性的比喻。你去菜市场买菜，预算和背包容量都有限，每个摊位上的菜重量和价格都不一样，你想知道怎么买能让袋子里的总价值最高。连续放松上界法就是：你先按“每斤价格”从高到低把所有菜往袋子里塞，直到塞不下为止，最后一个菜实在放不下整份，就跟老板商量“只称一部分”，按比例付钱。这样算出来的总价一定大于等于你实际能实现的最优总价，因为现实中没人会卖你半个土豆。但恰恰是这种“虚高”的上界，给了我们提前放弃某些摊位组合的底气。

1.2 上界估计的三种做法，谁更适合背包问题

上界函数的选取直接决定分支定界的效率，我在不同项目里试过三种，这里对比一下。

第一种是线性规划松弛，把整数变量放宽成连续变量，然后用单纯形法求松弛解。这个上界最紧，剪枝效果最好，但每次计算都要求解一个线性规划，代价太高，对背包这种小场景属于杀鸡用牛刀。

第二种是“分数背包”上界，也是我在代码里采用的方案。先把所有物品按单位价值 (v_i / w_i) 降序排序，然后按顺序往剩余容量里塞：能整件装下就整件装，装不下最后一个物品时只按剩余容量比例计入价值，后面物品直接忽略。因为每个物品把整数改成可拆分后，可行域变大了，所以算出来的目标值一定大于等于整数背包的最优值。这个上界计算只需要一趟循环，开销极小，而且紧度在绝大多数算例上非常可观。

第三种是贪心启发式上界，直接按单位价值排序取前几个物品算出价值。这个方法算得很快，但它可能低估真实最优值，导致“该剪的没剪”甚至漏掉最优解，不能作为精确算法的剪枝依据。贪心只适合拿来快速生成一个初始可行解，用来提高早期剪枝率。

实战里我几乎固定使用第二种。它和物品排序天然配套，代码实现简单，而且剪枝效果足够支撑我在几个真实项目里的规模需求。下面的完整代码实现，也是基于这个思路展开的。

2. 背包问题的建模与解空间结构

正式写代码之前，先把数学模型摆出来，避免后面实现的时候概念混淆。我这里讨论的是最经典的 01 背包问题：有 (n) 个物品，每个物品 (i) 有重量 (w_i) 和价值 (v_i)，背包容量为 (W)，每个物品只能整体选或不选，目标是在总重量不超过 (W) 的前提下，让总价值最大。

数学形式可以写成：

[ \max \sum_{i=1}^{n} v_i x_i ]

约束条件：

[ \sum_{i=1}^{n} w_i x_i \le W, \quad x_i \in {0, 1} ]

其中 (x_i = 1) 表示选物品 (i)，(x_i = 0) 表示不选。

这个模型看起来平平无奇，但解空间却是指数级的。每个物品有两种状态，(n) 个物品就有 (2^n) 种组合。(n=30) 的时候超过十亿，(n=50) 的时候已经没法用“暴力枚举”这个词去想了。分支定界法的高明之处，就是不把整个解空间完整遍历一遍，而是通过剪枝策略把大部分解空间“证明”为不可能最优，从而大大压缩搜索范围。

2.1 决策树视角：每个物品分两条路

把 01 背包的解空间画成一棵二叉树，根节点表示“还没对任何物品做决定”。从根节点开始，每遇到一个物品，就分叉成两个节点：一个分支选择不拿当前物品，另一个分支选择拿走当前物品。这样一层一层往下走，等 (n) 个物品全部决策完，树的高度就是 (n)，叶子节点个数为 (2^n)。

举个例子，假设有 3 个物品，决策树的前两层的路径就是：根节点 → “不选物品1”或“选物品1”；再往下，“选物品1”的节点又会分裂成“选1不选2”和“选1选2”。最终所有叶子组成了全部可选组合。

分支定界的“分支”步骤，本质上就是对这棵二叉树做广度优先或深度优先遍历。只不过它不会盲目地走完整棵树，而是在扩展节点前先做两次判断：第一，当前节点代表的重量是否已经超过背包容量，如果超了，这个节点就是死路，剪掉；第二，当前节点继续往下走的最大可能价值是否已经低于已知最优解，如果低了，同样剪掉。

2.2 连续放松上界：菜市场买菜的比喻

上界函数在分支定界里的地位，等同于剪刀的锋利程度。我要给每个节点算一个“从当前状态继续往下走，理论上最多能拿多少价值”的上限值。

算法步骤是这样的：假设当前节点已经确定选择了若干物品，剩余容量是 (R)，接下来还没决策的物品按照单位价值 (v_i / w_i) 从高到低排序。我从单位价值最高的物品开始，依次尝试把物品“塞”进剩余容量 (R) 里。如果能放得下整件，就直接算入价值并扣掉重量；如果放不下整件，就只按比例计入一部分价值，比如剩余容量只剩 (3)，而当前物品重量是 (5)，价值是 (10)，那这一层最多贡献 (10 \times 3 / 5 = 6)。计算到这里就可以停止了，因为剩余容量已经为 0。

这个值为什么叫上界？因为它允许了“把物品拆开”这个现实中不存在的操作。整数背包要求每个物品要么全拿要么全不拿，而连续放松允许把最后一个物品只拿一部分，可行域变大了，目标函数值自然只会更高。所以它一定是实际最优解的一个上界，用它来做剪枝判定是安全的。

这里要特别强调一个新手容易犯的错误：上界函数的计算必须基于“当前节点已经消耗的重量”来推算剩余容量，而不是从头开始算。

2.3 分支定界求解 01 背包的完整流程

把分支、定界两个关键词串起来，标准流程就这么几步。

第一步，把所有物品按单位价值从高到低排序。排序的目的是让上界函数算得快且紧，因为单位价值高的物品在连续放松里会被优先塞入，排序后可以顺序扫描。

第二步，初始化一个优先队列，队列节点代表一个搜索状态，包含当前决策到了哪个物品、当前总重量、当前总价值、上界值。根节点的上界就是所有物品按分数背包规则算出的值。

第三步，从优先队列里取出上界值最大的节点。如果这个节点的上界已经小于等于当前已知最优解，说明它和它下面的所有分支都不值得再看了，直接丢弃。

第四步，检查当前节点是否已经决策完所有物品。如果是，说明是一条完整路径，更新最优解；如果还没决策完，就扩展出两个子节点：一个不选当前物品，一个选当前物品（前提是选完不超重）。每生成一个子节点，就立刻计算它的上界，上界有潜力的才重新压回优先队列。

第五步，重复第三、第四步，直到优先队列为空。算法结束时记录的最优解就是全局最优。

这个流程真正聪明的地方在于，优先队列每次弹出的都是当前“看起来最有希望”的节点。如果某个分支的上界很低，它就一直排在队尾，甚至永远不会被弹出；如果某个分支的上界高于当前最优，它才有机会被继续展开。整个搜索树看起来像是被从上往下、从左往右“啃”下来，但大量边角料在还没被啃到之前就已经被证明是废料了。

3. 完整 C++ 实现：优先队列 + 限界函数

代码我用 C++17 写了，完整可编译运行，状态压缩用整型位掩码实现，方便理解且适合笔试场景。如果你在生产环境里处理 (n) 很大的情况，把位掩码换成vector<bool>或者bitset就行。

3.1 数据结构设计和完整代码

先看代码，每一段后面我会补充设计理由。

#include <bits/stdc++.h> using namespace std; struct Item { int idx; // 原始编号，排序后会打乱，必须保留 int w; // 重量 int v; // 价值 double ratio; // 单位价值 v / w }; struct Node { int curIdx; // 当前待决策的物品下标 int curW; // 当前总重量 int curV; // 当前总价值 double ub; // 从当前节点继续往下的价值上界（含 curV） int mask; // 位掩码，第 i 位为 1 表示已选中排序后的第 i 个物品 bool operator<(const Node& other) const { return ub < other.ub; // 让上界大的节点先出队 } }; double calcBound(int idx, int curW, int n, int cap, const vector<Item>& items) { double total = 0.0; int remain = cap - curW; for (int i = idx; i < n; ++i) { if (items[i].w <= remain) { total += items[i].v; remain -= items[i].w; } else { total += items[i].v * 1.0 * remain / items[i].w; break; } } return total; } int branchAndBound(int n, int cap, vector<Item>& items, int& bestMask) { sort(items.begin(), items.end(), [](const Item& a, const Item& b) { return a.ratio > b.ratio; }); int bestV = 0; bestMask = 0; priority_queue<Node> pq; Node root; root.curIdx = 0; root.curW = 0; root.curV = 0; root.mask = 0; root.ub = calcBound(0, 0, n, cap, items); pq.push(root); while (!pq.empty()) { Node cur = pq.top(); pq.pop(); if (cur.ub <= bestV + 1e-9) continue; if (cur.curIdx == n) { if (cur.curV > bestV) { bestV = cur.curV; bestMask = cur.mask; } continue; } Node skip = cur; skip.curIdx++; skip.ub = calcBound(skip.curIdx, skip.curW, n, cap, items) + skip.curV; if (skip.ub > bestV + 1e-9) pq.push(skip); Node take = cur; Item& it = items[cur.curIdx]; if (cur.curW + it.w <= cap) { take.curIdx++; take.curW += it.w; take.curV += it.v; take.mask |= (1 << cur.curIdx); take.ub = calcBound(take.curIdx, take.curW, n, cap, items) + take.curV; if (take.ub > bestV + 1e-9) pq.push(take); } } return bestV; } int main() { int n = 4, cap = 10; vector<Item> items = { {0, 2, 6, 0}, {1, 3, 8, 0}, {2, 4, 10, 0}, {3, 5, 12, 0} }; for (int i = 0; i < n; ++i) { items[i].ratio = (double)items[i].v / items[i].w; } int bestMask = 0; int bestV = branchAndBound(n, cap, items, bestMask); cout << "最优价值: " << bestV << endl; cout << "选中的原始物品编号: "; for (int i = 0; i < n; ++i) { if (bestMask & (1 << i)) { cout << items[i].idx + 1 << " "; } } cout << endl; return 0; }

3.2 Node 结构体的设计逻辑

Node是我整个实现里最核心的结构。它不仅要记录“当前状态”，还要记录“怎么走到这个状态的”，否则算法跑到最后即使找到了最优解，也不知道选的是哪些物品。curIdx表示接下来要决策的物品下标，注意这里存的是排序后的下标，不是原始输入顺序。curW和curV分别维护当前已选物品的总重量和总价值，每次扩展节点时同步更新。mask用位掩码记录路径选择，用于最后输出方案。

operator<的重载是整个搜索顺序的关键。priority_queue默认是最大堆，但比较逻辑来自<运算符。我把ub大的节点判定为“更小”，这样堆顶弹出的就是上界最大的节点。有人会问，为什么一定要弹出上界最大的？因为上界最大的节点最有希望通向更优解，优先展开它能尽快提高bestV。bestV提高得越早，后面被剪掉的分支越多，整体搜索效率越高。这属于分支定界里“深度优先 + 最佳优先”的混合策略。

3.3 calcBound 上界函数的实现细节

calcBound函数接收四个参数：当前待决策的物品下标idx、当前已经消耗的重量curW、物品总数n、背包总容量cap。它从下标idx开始，按已排好的单位价值顺序往剩余空间里塞物品。

函数内部维护一个变量remain，初始值是cap - curW，表示剩余容量。循环里如果当前物品能整件放下，就累加整个价值并扣减剩余容量；如果放不下整件，就按比例计入一部分价值，然后立刻break。这里补一句，计算比例价值时我用v * 1.0 * remain / w，把其中一个因子转成double，避免整数除法直接把小数部分丢掉。

这个函数返回的是从当前节点往后“还能净增加的价值上限”，不包含当前节点已经积累的curV。所以每次生成子节点计算ub时，代码里都写成了calcBound(...) + curV。这一点非常重要，很多版本在抄代码的时候会漏加curV，导致上界被严重低估，原本不该剪的节点被错误剪掉，直接丢失最优解。

3.4 主循环里的剪枝和扩展顺序

主循环做的事情，本质上是“弹出 → 判断 → 扩展 → 压回”四件事，但顺序里藏着几个容易踩坑的地方。

弹出节点后，第一件事是判断cur.ub <= bestV + 1e-9。这里的1e-9是浮点数比较的容差，防止因为精度误差把某个上界恰好等于bestV的节点误剪。很多书上直接写<=，在纯整数环境下没问题，但一旦物品价值和重量是浮点数输入，就会有概率出错。

然后判断cur.curIdx == n。如果成立，说明所有物品都已经决策完了，这个节点是一个完整的可行方案。此时直接比较curV和bestV，更新最优解和最优掩码。

扩展子节点时，我选择先压skip再压take，这个顺序不是随意的。因为同一父节点的两个子节点，take分支通常比skip分支拥有更大的上界，先压入skip不会立即弹出，而take分支后压入却会排在堆顶，从而优先被探索。这个顺序配合优先队列，能更快找到高质量可行解，后续剪枝力度也更大。

在生成take子节点之前，代码判断cur.curW + it.w <= cap。这个剪枝叫可行性剪枝，和上界剪枝互补。超重的节点连进入优先队列的资格都没有，能省掉非常多的无效展开。

4. 跑一个具体算例：上界演进与剪枝验证

光看代码可能还不够直观，我拿一个简单算例手动把搜索树的关键节点走一遍。这个算例很简单，但每一步的数值都能对上，你可以对照代码去验证。

4.1 算例设定与排序

假设背包容量 (W = 10)，有 4 个物品，原始信息如下。

这里物品本来就已经按单位价值降序排列了，所以排序步骤不会改动顺序。实际项目中原始顺序往往是乱的，排序之后再靠idx字段找回原始编号。

根节点的上界计算过程：按顺序扫描物品1、2、3、4。物品1、2、3可以整件装入，总重量 (2+3+4=9)，剩余容量 1，总价值 (6+8+10=24)。物品4重量 5，放不下整件，按比例贡献 (12 \times 1 / 5 = 2.4)。根节点上界 (= 24 + 2.4 = 26.4)。

4.2 关键搜索路径推演

优先队列初始只有根节点，值为(curW=0, curV=0, ub=26.4)，弹出它并生成两个子节点：不选物品1的skip节点，上界为 25.2；选物品1的take节点，上界为 26.4。由于take上界更大，下一轮优先弹出它。

继续扩展take节点，生成“选1不选2”和“选1选2”两个子节点。“选1选2”这个路径重量累计到 5，价值累计到 14，剩余容量 5，后续还能塞进物品3和物品4的分数部分，上界仍然是 26.4。

继续往下，走到“选1选2选3”这个节点时，重量为 9，价值已经累计到 24，剩余容量 1。此时后面的物品4无论怎么算，最多再贡献 2.4 的价值，上界 (= 26.4)。这个节点本身已经是一个完整可行方案，因为如果尝试再选物品4就超重，生成take子节点时会被可行性剪枝挡住；而生成skip子节点后，curIdx到达 4，下一轮弹出时就会触发cur.curIdx == n的分支，把bestV更新为 24。

看一下其中一个典型的剪枝行为：根节点的skip分支，也就是“不选物品1”，上界是 25.2。它虽然高于 24，但只高出 1.2，优先队列会一直把它压着。后来算法从其他方向找到了价值 24 的最优解，等到这个节点终于被弹出时，它的上界 (25.2) 仍然大于 24，于是不会被立即剪掉，而是被继续展开。展开后因为后续没有能超过 24 的方案，所有子节点最终都会被剪枝或自然淘汰。这就是分支定界的效果：该搜的路线一条不落，不该搜的路线在早期就被批量砍掉。

下面这张表整理了搜索过程中的几个关键节点，方便你对照代码调试。

最终输出最优价值 24，选中的原始物品编号是 1、2、3。

4.3 输出方案正确性的验证

代码运行结果里，bestMask记录的其实是排序后的下标状态。输出阶段通过items[i].idx + 1还原原始编号。这一点看似不起眼，实际项目里一旦省略，排完序后你输出的选品方案就会跟真实物品对不上号。

我在实际调试时习惯再加一段核对逻辑：把bestMask选出来的物品重量求和，断言它不超过背包容量，同时把价值和bestV再次比对。这个断言看起来多余，但能在一开始就拦住排序、掩码、上界这三处最隐晦的 bug。正式代码里加一个assert成本极低，收益却很高。

5. 分支定界法与动态规划的选型对比

写到这里，肯定有人想问：背包问题不是有动态规划解法么，而且代码还更好写，为什么要绕这么大一圈用分支定界？这个问题的答案，我在文章开头提过一嘴，这里展开讲清楚，顺便给出一套选型建议。

5.1 动态规划 vs 分支定界：容量尺度与状态维度是关键

经典的 01 背包动态规划转移方程是：

[ dp[j] = \max(dp[j], dp[j - w_i] + v_i) ]

用一维滚动数组就能搞定，时间复杂度 (O(nW))，空间复杂度 (O(W))。当背包容量 (W) 在几千、几万这个量级时，动态规划几乎是碾压级的存在，代码短、思路直、不容易错，我在 LeetCode 刷题时也一直首选它。

但动态规划有一个致命前提：状态空间必须能开得下。如果 (W = 10^8)，哪怕空间压缩到一维数组，光是int数组就要占用 400MB 内存，这在绝大多数服务器上都是不可接受的。而分支定界法不依赖背包容量，它依赖搜索树的剪枝效率，内存占用只跟实际展开的节点数挂钩。同样是 30 个物品，容量百万级，分支定界可能在展开几千个节点后就收敛了，动态规划却直接卡死。

另一个关键区别是“约束类型”的兼容性。动态规划处理多维背包时，状态每一维都要开一整个数组，三维、四维叠加起来就是灾难。分支定界的模型只需要改两个地方：一是在节点扩展时增加“是否满足额外约束”的可行性判断，二是在上界函数里把不满足约束的路径提前封死。它不需要改变整体框架，所以扩展性天然更好。

5.2 什么场景下我首选分支定界

我根据自己的项目经验，整理了一套选型标准，分享出来供参考。

• 如果物品数量 (n \le 100) 且背包容量 (W \le 10^6)，优先考虑动态规划，简单可靠。
• 如果物品数量 (n) 在 20 到 50 之间，背包容量巨大，或者存在多重约束，优先考虑分支定界，先用启发式生成一个初始可行解，再挂上界剪枝。
• 如果 (n) 超过 80，纯粹的精确分支定界也会变慢，此时需要上界函数足够紧，或者考虑元启发式算法求近似解。
• 如果场景是笔试或面试，题目描述自带“背包容量”这个变量，而且范围不超过 1000，直接写动态规划。

我在那个调度项目里，订单数在 25 个左右，但每一单还有重量之外的长宽高体积约束，就属于典型的分支定界主场。后来我还接到过一个相似的需求，约束改成了“某些品类必须同时选择或同时不选”，我把可行性判断加进节点扩展里，上界函数只增加了一个互斥检查，代码结构完全没动，短短几十行就扩展完了。如果当初硬写动态规划，光是状态设计就够我喝一壶。

6. 实现中的坑与小技巧

最后这部分是重点中的重点，所有代码都不是一次通过的，下面这些坑我几乎全踩过，有些甚至是在生产环境跑了几周之后才暴露出来的。写出来帮你避开。

6.1 double 取整的精度陷阱

上界函数返回的是double，而bestV是int，在比较cur.ub <= bestV + 1e-9时已经做了容差处理。但还有一个隐藏的坑出现在重量或价值带有小数点的场景里。如果重量是2.9，计算剩余容量后出现类似10 - 7.1 = 2.8999999999999995的值，直接拿去和物品重量比较，会错误地认为容量不够。我的习惯是，所有涉及浮点容量和重量的地方，都用eps = 1e-9修正，比如if (remain + eps >= items[i].w)。计算选入后的重量，也要写成int(curW + it.w + 0.5)之类的四舍五入，或者干脆在输入阶段就让重量统一变成整数（乘以一个公约数）。

6.2 上界函数里最隐蔽的 bug：同一物品被重复计入

这是我见过次数最多的实现错误。很多人写calcBound时没有把“当前物品下标idx”作为搜索起点，而是从0开始重新扫描所有物品。这么一来，在当前节点之前已经被决策过的物品，会再一次被算进上界里，导致上界虚高。上界虚高的后果是剪枝效率大幅下降，极端时会退化成近乎回溯法的全遍历。

正确的写法必须严格从idx开始，而且这个idx要在每次生成子节点时分毫不差地往前推进。我在代码里单独把skip.curIdx++和take.curIdx++写出来，就是在强调“当前物品一旦决策完，下一次循环就不能再看了它”。

6.3 全选可行时的提前返回

如果所有物品的总重量加起来都不超过背包容量，最优解显然是把所有物品都选上，这时直接返回结果就好，不需要进入搜索流程。你可能会觉得这是多余的优化，但我在一个实际项目里见过，容量开得极大，输入数据经常出现“所有订单加起来还装不满车”的情况。这种情况如果不提前处理，分支定界会把整棵搜索树完整走一大半，白白耗费大量时间。在函数入口处加一个重量总和判断，几行代码就能避免灾难。

6.4 从单背包到多背包的扩展思路

生产环境里经常遇到比 01 背包更麻烦的问题，最常见的是“多背包问题”：有若干个背包，容量各不同，每个物品只能放进一个背包。分支定界法扩展到这个场景并不难：把节点里的curW扩展成一个容量数组，每个物品决策时多一层“放进哪个背包”的分支；上界函数需要估算所有背包剩余容量的潜在价值总和，按单位价值排序后依次填入所有背包。这个扩展虽然会让搜索树变宽，但剪枝逻辑完全不变，框架不会有颠覆性改动。

我自己在扩展多背包时吃过一次亏：多个背包的剩余容量不相同，排序后的物品如果只按“单位价值”统一填充，会遗漏“某个背包容量太小、只能塞进多个小物品”的情况。后来我改成对上界函数里的“按背包逐个填充”做了精细化处理，搜索效率才回到正常水平。这个经验告诉我，分支定界框架虽通用，但没有一劳永逸的万能上界函数，每个场景都需要根据约束特征去调校。

最后再分享一个我在实际使用中养成的习惯：写完代码第一件事，不是拿大算例测性能，而是先写一个暴力枚举的小函数，随机生成几千组小规模数据逐个对拍。分支定界这种“靠剪枝省时间”的算法，正确性必须靠对拍来兜底。只要小规模数据全部对得上，再拿去跑真实数据，心里才有底。这个习惯帮我挡掉了至少两次上界函数漏加curV的致命 bug，希望你也能用上。