01背包问题是我接触算法这么多年，最常拿来测试新思路的“试金石”。它表面简单到一句话就能说清楚：每个物品要么装进背包、要么不装，在总重量不超过背包容量的前提下，让总价值尽可能大。可一旦物品数量超过几十个，暴力枚举立刻变成天文数字；贪心算法快是快，却经常在最后一刻给出一个不是最优的答案；动态规划在容量很大的时候，内存和时间又会双双爆炸。我第一次认真研究分支定界算法（Branch and Bound），就是被这样一组数据逼的：物品数量不算大，但背包容量到了千万级别，动态规划根本塞不下，贪心又无法保证最优。后来把分支定界吃透才明白，这类问题的核心不是“遍历所有方案”，而是如何尽可能少地遍历。这篇文章从问题建模讲起，逐步拆解分支定界的三件套——分支、定界、剪枝，然后给出一份可以直接跑的 Python 实现，最后聊聊我在不同规模算例上的实测体会，以及它和动态规划、回溯法之间到底该怎么选。
1. 为什么01背包看起来简单，却容易在数据量面前翻车
1.1 问题本质与数学建模
先把问题形式化。给定 n 个物品，第 i 个物品的重量是 w_i、价值是 v_i，背包容量为 C。引入 0-1 决策变量 x_i，x_i = 1 表示装入，x_i = 0 表示不装，那么模型就是：
最大化：Σ v_i * x_i 约束： Σ w_i * x_i ≤ C x_i ∈ {0, 1}注意这里“0-1”是核心，它和“分数背包”有本质区别。分数背包允许把一个物品切开只装一部分，所以贪心按价值密度从高到低装就行了。而 01 背包不允许切割，一个物品只有“整件装”和“整件不装”两种状态，这就导致贪心失效：你可能为了装下一个密度很高的物品，被迫放弃一堆密度稍低但总价值更大的组合。
这种问题的复杂度属于 NP 难。从组合数学的角度看，n 个物品的选择方案一共有 2^n 种。n = 30 时是十亿级别，n = 50 时 2^50 已经超过一千万亿，普通机器上直接枚举是绝对跑不完的。
1.2 贪心失败现场与动态规划的内存困境
我见过不止一个初学者写完贪心代码之后对着结果发呆。举个反例：背包容量 10，三个物品分别为 (重量, 价值) = (6, 6)、(5, 5)、(5, 5)。按价值密度排序全部一样，贪心先装第一个，剩余容量 4，装不下任何剩下的，总价值 6。可实际上装后两个，总价值是 10，重量刚好也是 10。这就是 01 背包和分数背包最大的区别：它不是一个“按比例分配”的问题，而是一个“组合取舍”的问题。
动态规划能保证最优，时间复杂度 O(nC)，空间可以滚动到 O(C)。问题是，这个复杂度里的 C 是背包容量，不是物品个数。我实际遇到过 n = 500、C = 5000000 的输入，500 × 500 万就是 25 亿次操作，内存哪怕用滚动数组也要 500 万 × 4 字节约 20MB，时间却要好几秒甚至更久。当容量继续放大到亿级，DP 基本就废了。
分支定界算法在这个场景下就显得特别有价值：它不依赖容量 C 的大小，核心消耗取决于搜索树的节点数。只要上界函数设计得好、剪枝剪得及时，很多大规模实例在极短时间就能出最优解。这也是我决定深入实现它的原因。
2. 分支定界的三件套：分支、定界与剪枝的完整逻辑
2.1 解空间树：把“选/不选”铺成一棵二叉树
分支定界的第一步是把所有可能方案组织成一棵树。树的每一层对应一个物品的决策节点，从根节点出发，左分支表示“装入当前物品”，右分支表示“不装当前物品”。走到叶子节点，就得到一组完整的 0-1 选择方案。n 个物品的解空间树一共有 2^(n+1) - 1 个节点，叶子数是 2^n。
直接遍历这棵树就是回溯法，复杂度指数级。分支定界和朴素回溯的本质区别在于：回溯法把所有叶子都走一遍才能确定最优解，而分支定界在每个内部节点先估算“如果继续往下走，最高能拿到多少价值”，一旦这个估算值比当前已知最优解还要差，就果断砍掉整个子树，根本不用进去。
2.2 定界的几何直觉：先假设“能切开”，再慢慢收紧
分支定界里，上界函数是整个算法的灵魂。常见的做法是把 01 背包“松弛”成连续背包问题：允许当前节点后面的物品按任意比例装入。因为约束放宽了，松弛问题的最优解一定不小于原问题任何一个可行解的价值，所以它可以作为原问题的合法上界。
这个上界还有一个特别好的性质：连续背包问题用贪心就能解。把剩余物品按价值密度从高到低排好，能整件装的先整件装，装到最后一个物品时如果剩余容量不够，就按比例取一部分。算出来的总价值，就是当前节点继续往下探索的价值天花板。
更有意思的是整数取整。如果所有价值和重量都是正整数，那么任意一个整数可行解的价值必然是整数，而上界如果是 13.67，那它真正的整数上界最多是 13。把上界向下取整，在实际剪枝中往往能多砍掉相当一部分节点。
2.3 三个可以剪枝的地方，别漏掉任何一个
我用一个具体例子演示。假设 4 个物品：(重量, 价值) = (2, 3)、(3, 4)、(4, 5)、(5, 8)，背包容量 9。所有方案里最优的是装物品 3 和物品 4，总重量 9，总价值 13。
首先按价值密度从大到小排序，排序后顺序是：物品 4（密度 1.6）、物品 1（密度 1.5）、物品 2（密度 1.33）、物品 3（密度 1.25）。
根节点的上界：按密度装满 9 容量，物品 4 整装、物品 1 整装，剩 2 容量只能装 2/3 个物品 2，上界 = 8 + 3 + 4×2/3 ≈ 13.67，取整为 13。
初始最优解 best_value 设为 0，开始深度优先搜索。整个过程可以简化成下面这棵文本树：
根节点：上界13 ├─ 左：装物品4，重量5，价值8，上界13 │ ├─ 左：装物品1，重量7，价值11，上界13 │ │ └─ 右：不装物品2，之后只能走到价值11，best更新为11 │ └─ 右：不装物品1，重量5，价值8，上界13 │ ├─ 左：装物品2，重量8，价值12，best更新为12 │ └─ 右：不装物品2，重量5，价值8 │ └─ 左：装物品3，重量9，价值13，best更新为13 └─ 右：不装物品4，上界 = 3+4+5 = 12，12 ≤ best=13，剪枝可以看到，右分支在根节点就被砍掉了，因为不管后面怎么选，价值都不可能超过 12。整个搜索只访问了 12 个节点，而朴素回溯会访问全部 31 个节点。当 n 变大，这种差距会被指数级放大。
3. 上界函数的底层思考：连续背包松弛为什么能用、怎么用
3.1 线性规划松弛：允许“半个物品”的妙处
很多人第一次看到连续背包松弛都会有一个疑问：明明 01 背包不允许装半个物品，为什么拿“允许装半个”的模型来当上界，不会给出错误的剪枝判断？
关键在于“上界”的性质。我们要保证一件事：任何从当前节点出发的完整方案，其价值都不可能超过上界函数算出来的值。连续背包问题的可行域比 01 背包更大，所有整数可行解都是松弛问题的可行解。因此，松弛问题的最优值一定是整数问题最优值的上界，这个逻辑是严格成立的。用一句话概括：放宽约束只会让最优值变大，绝不会变小，所以它是一个“不会漏掉最优解”的天花板。
连续背包问题的贪心最优性也可以用交换论证来理解：假设有两个物品 A 和 B，A 的密度比 B 高。如果一个可行解里装了 B 的一部分重量 d，却在 A 还没装满时留有空位，那么把 d 这部分重量换成等重的 A，重量不变、价值更高。反复做这种交换，最终的形态必然是密度从高到低装满，所以贪心顺序正确。
3.2 从13.67到13：取整技巧带来的额外剪枝力
取整技巧非常实用，但有两件事必须注意。
第一，只有所有物品的价值、重量都是整数时，才能放心对 bound 向下取整。整数可行解的价值累加后必然是整数，而连续松弛上界哪怕算出 13.67，实际上你最多能凑出的整数价值也不会超过 13。可如果物品价值本身是浮点数，直接 int() 可能会把上界截到一个不可达的下方，造成误剪枝。我在实现里默认所有输入都是正整数，所以会用int(bound(...)) <= best_value作剪枝条件；如果碰到浮点价值，改成bound(...) <= best_value + 1e-9更稳妥。
第二，取整时必须向下取整，不能四舍五入。13.67 四舍五入成 14 之后，上界被抬高了，剪枝条件变得更难满足，等于削弱算法效果；向下取整才是安全的紧化。
3.3 上界计算的代码实现要点
上界函数的实现逻辑很直白：
def bound(start, cur_w, cur_v): remain = capacity - cur_w upper = cur_v i = start while i < n and items[i][0] <= remain: upper += items[i][1] remain -= items[i][0] i += 1 if i < n and remain > 0: upper += items[i][1] * (remain / items[i][0]) return upper一个容易被忽略的性能优化：当剩余容量还能装下从 start 到末尾的所有物品时，按密度贪心并没有意义，此时上界就是当前价值加上剩余物品价值总和。这行判断可以用后缀和数组提前算好，虽然能省的时间不多，但在节点数上百万时，能减少不少浮点乘除和循环开销。
另外要强调，上界函数计算越紧，剪枝效果越好，但计算量也会增大。连续背包松弛是目前性价比最高的选择：它只需要一次线性扫描，还能配合我们已经做好的密度排序直接使用，不需要额外数据结构的维护。
4. 一份能跑的Python求解器实现与核心代码逐段拆解
4.1 预处理：为什么必须先按价值密度排序
分支定界对物品做密度降序排序，有三个好处：
一是上界函数计算连续背包解时，天然依赖密度从高到低的顺序，排序之后直接按顺序扫描即可。二是在搜索过程中，先考虑密度高的物品，更容易在早期形成质量较好的可行解。比如根节点左边分支装上密度最高的物品，往往很快就逼近最优值，best_value 提升得快，后续剪枝条件更容易满足。三是排序不会改变最优解本身，因为解空间本质上是在枚举所有 0-1 组合，顺序调整并不影响组合的完整性。
我在代码中使用(weights[i], values[i], i)三元组保存原始下标，排序时只排三元组列表，这样排序后依然能回溯每个物品的原始位置，最终构造出正确的选择掩码。
4.2 深度优先搜索与剪枝代码
完整求解器如下：
def solve_01knapsack_bnb(weights, values, capacity): n = len(weights) items = sorted( [(weights[i], values[i], i) for i in range(n)], key=lambda x: x[1] / x[0], reverse=True ) best_value = 0 best_mask = [0] * n node_count = 0 def bound(start, cur_w, cur_v): remain = capacity - cur_w upper = cur_v i = start while i < n and items[i][0] <= remain: upper += items[i][1] remain -= items[i][0] i += 1 if i < n and remain > 0: upper += items[i][1] * (remain / items[i][0]) return upper def dfs(idx, cur_w, cur_v, chosen): nonlocal best_value, best_mask, node_count node_count += 1 if cur_v > best_value: best_value = cur_v best_mask = [0] * n for orig in chosen: best_mask[orig] = 1 if idx >= n: return if int(bound(idx, cur_w, cur_v)) <= best_value: return w, v, orig_i = items[idx] if cur_w + w <= capacity: dfs(idx + 1, cur_w + w, cur_v + v, chosen + [orig_i]) dfs(idx + 1, cur_w, cur_v, chosen) dfs(0, 0, 0, []) return best_value, best_mask, node_count代码里有一个容易被忽略的顺序：进入节点后，先做“价值更新”，再做“上界剪枝”。这样设计是有意的。当递归从更深层返回到当前节点时，全局 best_value 可能已经被某个可行解刷新过了，此时再算上界剪枝才有意义。如果先剪枝再更新，部分子树就可能被一个偏低的 best_value 错误放过，导致整体搜索量变大。
4.3 记录最优解：从chosen列表到最终掩码
很多教程只返回最优值，不返回选中的物品集合，这对实际项目来说不够用。我用chosen列表保存从根到当前节点“装入”的物品的原始下标，每当找到一个更优价值时，就重新生成一个长度为 n 的全 0 掩码，把 chosen 里的下标都置为 1。
这种方式逻辑清晰，代价是每次更新最优解都要 O(n) 复制数组。当 n 达到几万时，频繁更新可能拖慢速度。另一种做法是维护一个和物品数等长的选择数组，在递归中用“选/不选”原位更新，叶子节点时统一拷贝一次。我推荐先跑通当前版本，再根据性能瓶颈决定要不要优化。
4.4 标准算例演示
用之前的例子验证：
weights = [2, 3, 4, 5] values = [3, 4, 5, 8] capacity = 9 value, mask, count = solve_01knapsack_bnb(weights, values, capacity) print("最优价值:", value) print("选择掩码:", mask) print("物品原始下标:", [i for i, x in enumerate(mask) if x == 1]) print("探索节点数:", count)输出应该是：
最优价值: 13 选择掩码: [0, 0, 1, 1] 物品原始下标: [2, 3] 探索节点数: 12注意掩码[0, 0, 1, 1]对应原始物品 3 和物品 4，总重量 4 + 5 = 9，总价值 5 + 8 = 13。整个搜索只访问 12 个节点，远小于 31 个节点的全遍历量。
5. 大规模实测：分支定界、动态规划与回溯法的选型边界
5.1 节点数与上界质量的关联
分支定界的实际表现高度依赖数据特征，我把它分成两类典型场景。
一类是“强相关”数据。价值与重量强相关，比如价值 = 2 × 重量 + 随机小扰动。这种情况下，连续背包松弛算出的上界和真正整数最优解非常接近，剪枝异常迅猛。我实测过 n = 200、容量 5000 的强相关数据，很多情况下节点数只有几千，毫秒级出结果。
另一类是“弱相关”数据。价值和重量基本独立随机生成，比如重量随机取 1 到 100，价值随机取 1 到 200。此时连续背包松弛的上界会明显虚高，剪枝能力大幅下降，节点数可能膨胀到几十万甚至百万级。n = 60、容量 1500 的弱相关数据，就要做好它跑好几秒的心理准备，而同样数据用动态规划 O(60×1500) 只要一个 O(nC) 小表就解决了。
所以分支定界并不是“更快的最优求解器”，它是“在某些数据分布下特别高效的最优求解器”。动手之前，先看一下你的数据是重相关还是弱相关，才能判断要不要选它。
5.2 分支定界、动态规划、回溯暴力的适用边界对照
我把三种精确求解方法放在一张表里比较：
| 方法 | 时间复杂度 | 空间复杂度 | 强项 | 明显短板 |
|---|---|---|---|---|
| 回溯暴力 | 最坏 O(2^n) | O(n) | 实现最简单 | 几乎不剪枝，n > 30 就吃力 |
| 分支定界 | 平均远小于 2^n，最坏 O(2^n) | O(n)（递归栈） | 不依赖容量，数据强相关时极快 | 弱相关数据可能退化指数级 |
| 动态规划 | O(nC) | O(C) 可滚动 | 稳定可预测，小容量场景最优 | 容量 C 大时内存和耗时爆掉 |
从工程角度，我一般这样选型：容量 C 和物品种类 n 都在可接受范围，直接上 DP，稳定省心。C 特别大、但物品数据有明显密度差异，上分支定界。数据是弱相关随机且 n 很大，那就别硬刚精确解，考虑启发式近似算法更现实。
5.3 我踩过的一个递归大坑
用 Python 写 DFS 分支定界时，有一个隐藏地雷：递归深度。n 达到 1000 以上时，默认递归上限很容易爆出RecursionError。解决办法有两个：一是在脚本开头设置sys.setrecursionlimit(10000)；二是改用显式栈。
显式栈还有一个额外好处：栈节点可以动态排序，方便实现后面要说的最佳优先搜索。不过代价是代码复杂度明显上升。如果你只是处理几百个物品，递归版本足够，没必要一开始就写显式栈。
6. 进阶玩法：Best-First搜索、下界强化与并行注意点
6.1 最佳优先搜索：优先处理最有希望的节点
深度优先搜索的优点是内存小，但它的“搜索路线”有时很盲目：明明某个节点的上界非常高，却因为递归路径的关系被排到很晚才处理；反而一些上界很低的节点，却因为出现在递归路径上被优先扩展了。
Best-First 策略用一个优先队列替代递归栈，每次取出上界最高的节点扩展。这样做的直接好处是：算法会非常快地走到一条高质量路径，并迅速刷新全局最优解。全局最优解变紧之后，其他节点的剪枝条件也就更容易满足。代价是优先队列需要保存大量节点，最坏情况下内存会指数增长。我通常只在解空间特别大、且上界质量参差不齐时使用 Best-First。
6.2 下界强化：起步时用一个好一点的初值
很多实现把初始 best_value 设为 0，这其实浪费了第一波剪枝机会。简单的改进是先跑一遍贪心算法，把一个可行解的价值作为初始下界。贪心解虽然不一定最优，但往往不会太差，尤其强相关数据下可能已经非常接近最优值。这样，搜索一开始就有了一把还算紧的尺子，剪枝效率立即提升。
更激进的做法是在每个节点内部再做一次局部贪心，基于当前已选物品继续往后挑选可行解，得到一个更精细的下界。但节点内部贪心会增加计算成本，对于节点数已经很少的强相关数据收益不大；对于弱相关数据，单纯加一个启发式下界也救不了虚高的上界。所以我的建议是：先用全局贪心当初始下界，跑一轮看效果，再决定要不要加节点级启发式。
6.3 并行化的现实考量
分支定界天然适合并行：根节点的左右分支彼此独立，可以分给不同工作线程去搜索。工程上需要维护一个全局共享的 best_value，任意工作线程发现更优可行解就原子更新；其他线程在剪枝判断时读取这个全局下界。
但并行分支定界有一个典型的坑：全局 best 更新可能有延迟，某个线程在上界已经能剪枝时，因为读到的 best 偏小，白白多搜了一整棵子树。要缓解这个问题，可以让工作线程定期同步全局 best，同时在每个子树搜索开始时重新读取一次。实际经验是，并行只能应对“弱相关大实例”带来的节点爆炸，而且加速比并不线性，很多时候 8 核只跑出 3 到 4 倍提升。如果节点数不大，并行反而因为线程同步开销变慢。我建议先把单核版本调到足够好，再考虑并行。
最后分享两个开发小技巧。第一，实现分支定界时，先写一个完全不带剪枝的回溯版，配合小规模暴力枚举或 DP 验证正确性，然后再加 bound 和剪枝，一步一确认。第二步专注调试剪枝条件，不然上界函数出错时，很难定位是“剪错了最优解”还是“搜索路径本身有 bug”。第二，调优时把 node_count 打印出来，观察剪枝前后节点数的变化。如果加了剪枝之后节点数还和暴力几乎一样，八成是上界太松或者排序没生效，这时候再回头检查上界函数，比盲目加并行要有效得多。
