如果你用动态规划写过0/1背包问题大概率会有类似的体验物品数量n只有几十个时一张二维表轻松拿下一旦n涨到几百上千背包容量W也跟着变成几十万dp[n][W]那张表无论时间还是空间都直接劝退。我前两年做物资打包调度时抽象出来的核心问题恰恰就是0/1背包物品数接近三千容量上限也很大动态规划根本没法跑。当时试了一圈替代方案里实现最直接、效果也最稳的就是分支界定法branch and bound也常译作分支定界法。这篇就把分支界定法解决背包问题的原理和代码实现完整拆开讲清楚从解空间树到剪枝机制再到一份可以直接复制的Python实现适合被大规模0/1背包、整数规划问题困扰的读者参考。1. 为什么背包问题需要分支界定法从解空间树说起1.1 三种经典背包解法和它们的边界背包问题算得上是组合优化里的hello world大部分人入门时接触的是这三种解法方法核心思路复杂度特征适用场景动态规划按容量一列一列填表dp[i][w] max(dp[i-1][w], dp[i-1][w-v[i]] p[i])O(nW)n和W都不太大尤其是W是几千以内的整数时贪心按价值密度从高到低塞塞不下就停止O(n log n)快速得到一个不错的可行解但没法保证最优回溯法DFS遍历所有选/不选组合剪掉超重分支指数级但常数小n在30以内、或者只要求可行解时动态规划看起来很美但它的复杂度里藏着那个容量W。当W非常大比如十万、百万dp表就完全失控了。而回溯法虽然能处理更大的n却要遍历到足够深的节点才敢确认最优很多时候跑完要等很久。分支界定法走的是另一条路线它不填表而是把问题的所有可能解组织成一颗树然后用一个上界来避免探索那些不可能产生最优解的子树。对大规模0/1背包问题这通常是纯Python代码里性价比最高的精确解法。1.2 分支界定法的核心直觉分支界定法的思路可以用一句话概括把所有选/不选每个物品的组合看成一颗满二叉树每个叶子节点对应一种完整方案。整棵树有2^n个叶子直接遍历等于枚举指数爆炸。但分支界定法不傻走到底它在遍历的过程中不断计算当前节点继续往下走理论最高能到多少价值。如果这个理论最高值已经比不上我们已经找到的一个可行解那这棵子树就没有继续探索的必要整枝砍掉。打个生活里的比方在衣橱里挑衣服出门预算有限、总价要求最高。你不会把所有组合都试穿一遍而是先按性价比排序选了几件之后发现就算把剩下的衣服全选上总价也超不过现在身上这身搭配那这条路直接放弃换别的组合试。分支界定法就是把这个人类直觉程序化。1.3 与回溯、动态规划的定位差异这三类方法解决的其实是同一个问题但思考方式不同回溯强调的是深度优先 约束剪枝。它适合找出所有解或者判断是否存在可行解。动态规划强调的是子问题重叠用空间换时间但它要求容量W是可控的整数。分支界定强调用上界引导搜索顺序。它通常配合队列使用目标是尽快找到一个好的可行解同时用上界证明其他方向不可能更好从而提前终止。所以分支界定法尤其适合那些最优解藏在很深处但大部分分支一眼看去就没希望的实例。它需要的不是填满整个表而是把每棵子树的上界算准、算紧。2. 分支界定的三个核心装置分支、定界、剪枝2.1 分支0/1背包的二叉决策树要在代码里实现分支界定法第一件事是明确分支长什么样。0/1背包的每个物品只有两个决策选或者不选。所以从根节点开始每处理一个物品就分裂出两个子节点。我习惯用level表示下一个待决策的物品下标根节点level0意味着第0个物品还没决策左分支表示不选当前物品右分支表示选当前物品处理完一个物品后level1。节点上除了level还必须记录三样东西profit当前已选物品的总价值。weight当前已选物品的总重量。include一个布尔列表记录之前每一步选了哪些物品。之前写过很多版本一开始没存include只存价值和重量结果跑完只能得到最优价值是多少却答不上来到底选了哪几件物品。后来所有节点都带一份选择记录虽然内存多花一点但至少结果可解释。2.2 定界用分数背包算一个尽量紧的上界分支界定法最关键的一步是算上界bound。上界表示从当前节点出发继续往后选物品理论上最多能拿到多少价值。一个经典做法是把当前节点的状态当作背包已经装了这么多然后从下一个物品开始按价值密度从高到低允许把物品拆开去填满剩余容量。这种做法就是分数背包问题的贪心解。之所以允许拆分是因为拆分放宽了约束。约束越宽松得到的最优值一定不会低于原问题的最优值。所以这个值天然就是一个合法的上界而且按密度贪心填满在连续情形下是最优的上界往往很紧。我拿后面测试用例里的数据提前演示一下。物品排序后依次是(价值6, 重量2)、(价值3, 重量2)、(价值6, 重量4)、(价值5, 重量6)、(价值4, 重量5)容量10。根节点bound计算过程当前价值 profit 0 当前重量 weight 0 从第0个物品开始装 装 (6, 2)价值 6重量 2 装 (3, 2)价值 9重量 4 装 (6, 4)价值 15重量 8 下一个物品 (5, 6) 装不下剩余容量 2 分数装入5 * (2/6) ≈ 1.6667 bound 15 1.6667 16.6667所以根节点上界约16.67。它大于实际最优解15因为最后一件被拆开了整数约束不允许这么做。这个大于等于最优解的性质就是剪枝判断的根本依据。2.3 剪枝超重剪枝与上界剪枝哪个先做有了上界之后剪枝就有两个抓手约束剪枝选当前物品会导致超重那这个分支根本不可行直接不生成子节点。界剪枝节点的bound best_profit其中best_profit是目前已经找到的最优可行解价值那么从这棵子树出发不可能找到更优解连入队都不用入。两个剪枝的顺序我的习惯是先做约束剪枝再做上界剪枝。倒不是效率差别有多大主要是约束剪枝更硬超重就是不行用不上界去判断而上界剪枝是需要best_profit支撑的best_profit越接近最优值剪枝越狠。还有一个细节剪枝条件用bound best_profit不是bound best_profit。因为如果上界只等于当前最优继续探索也不可能得到更好的结果直接剪掉没毛病。少了这个等号可能会多跑很多没意义的节点。3. 代码实现节点设计、上界计算与优先队列主循环3.1 节点定义与物品预处理我实现的版本在Python里跑数据结构用了一个简单的Node类class Node: def __init__(self, level, profit, weight, bound, include): self.level level self.profit profit self.weight weight self.bound bound self.include includeinclude存布尔列表True表示选当前层的物品。这里有个容易踩的坑生成子节点时如果用node.include.append(True)这种写法会改掉父节点和其他兄弟节点的数据。必须用node.include [True]或copy.copy的方式生成新列表。预处理阶段要按价值密度降序排序。这一步不是可选项而是必需项。因为bound计算时用贪心装填如果物品不是按密度排好的while循环里从当前level开始往后贪心就是错的。items [(values[i], weights[i], i) for i in range(n)] items.sort(keylambda x: x[0] / x[1], reverseTrue)x[0] / x[1]算的是单位重量价值也就是价值密度。排序后原来的下标i仍然保存在元组第三位这样最终输出结果时能把排序后的选择映射回原始物品的下标。3.2 上界函数从当前状态继续贪心上界函数的实现是整个算法的灵魂。我的写法里它接收当前节点的level、profit、weight然后返回一个float类型的上界def calc_bound(level, profit, weight): if weight capacity: return 0 bound_profit profit total_weight weight i level while i n and total_weight items[i][1] capacity: total_weight items[i][1] bound_profit items[i][0] i 1 if i n: bound_profit (capacity - total_weight) * items[i][0] / items[i][1] return bound_profit这个函数做了三件事如果当前重量已经等于或超过容量说明这个节点本身不可行了上界直接返回0。从level开始不断尝试整件装入物品直到装不下为止。对第一个装不下的物品按剩余容量比例取它的一部分价值作为分数部分的贡献。注意最后一项是浮点数。由于物品的价值通常是整数而分数背包的松弛解会允许小数因此bound结果天然带小数。这是合理的因为上界本来就允许超过整数最优值。但如果后续做剪枝比较时直接用浮点精度问题可能带来边际问题这个我在第5部分详细说。3.3 优先队列驱动的LC搜索主循环搜索策略上我选择LC搜索Least Cost / Best First。具体做法是把所有活节点放进一个优先队列每次都取出上界最大的节点进行扩展。为什么用优先队列而不是普通FIFO队列因为上界大的节点意味着这棵子树里更可能有最优解优先扩展它能更早找到一个好的可行解best_profit更新得更快剪枝力度也随之变大。用FIFO的话节点按层扩展可能先处理一堆上界很低的废节点导致搜索空间膨胀。Python的heapq默认是小顶堆我用负数把取最大上界这个需求转化成取最小负数heapq.heappush(pq, (-node.bound, node))主循环结构while pq: _, node heapq.heappop(pq) if node.level n: if node.profit best_profit: best_profit node.profit best_include node.include[:] continue if node.bound best_profit: continue # 不选当前物品 child_include node.include [False] child_bound calc_bound(node.level 1, node.profit, node.weight) if child_bound best_profit: child Node(node.level 1, node.profit, node.weight, child_bound, child_include) heapq.heappush(pq, (-child_bound, child)) # 选当前物品 new_weight node.weight items[node.level][1] if new_weight capacity: child_include node.include [True] child_profit node.profit items[node.level][0] child_bound calc_bound(node.level 1, child_profit, new_weight) if child_profit best_profit: best_profit child_profit best_include child_include[:] if child_bound best_profit: child Node(node.level 1, child_profit, new_weight, child_bound, child_include) heapq.heappush(pq, (-child_bound, child))每弹出一个节点先判断是否到达叶子层不是叶子层就先做界剪枝。然后生成不选和选两个子节点。选的那个分支还要额外检查超重问题超重就直接跳过这也是一种剪枝。关于best_profit的初始值我建议设成-1而不是0。原因是如果所有物品总重量都超过容量最优解是什么都不选价值为0best_profit-1能保证第一个可行的叶子节点哪怕价值是0也会被正确记录。4. 完整代码、测试用例与最优性验证4.1 一份可直接运行的完整实现把上面几个部分拼起来就是一份完整的Python代码。涉及NumPy以外没有任何第三方依赖Python 3.8及以上直接能跑import heapq class Node: def __init__(self, level, profit, weight, bound, include): self.level level self.profit profit self.weight weight self.bound bound self.include include def knapsack_branch_bound(capacity, values, weights): n len(values) items [(values[i], weights[i], i) for i in range(n)] items.sort(keylambda x: x[0] / x[1], reverseTrue) best_profit -1 best_include [] def calc_bound(level, profit, weight): if weight capacity: return 0 bound_profit profit total_weight weight i level while i n and total_weight items[i][1] capacity: total_weight items[i][1] bound_profit items[i][0] i 1 if i n: bound_profit (capacity - total_weight) * items[i][0] / items[i][1] return bound_profit root_bound calc_bound(0, 0, 0) root Node(0, 0, 0, root_bound, []) pq [] heapq.heappush(pq, (-root_bound, root)) while pq: _, node heapq.heappop(pq) if node.level n: if node.profit best_profit: best_profit node.profit best_include node.include[:] continue if node.bound best_profit: continue # 不选当前物品 child_include node.include [False] child_level node.level 1 child_bound calc_bound(child_level, node.profit, node.weight) if child_bound best_profit: child Node(child_level, node.profit, node.weight, child_bound, child_include) heapq.heappush(pq, (-child_bound, child)) # 选当前物品 new_weight node.weight items[node.level][1] if new_weight capacity: child_include node.include [True] child_profit node.profit items[node.level][0] child_bound calc_bound(child_level, child_profit, new_weight) if child_profit best_profit: best_profit child_profit best_include child_include[:] if child_bound best_profit: child Node(child_level, child_profit, new_weight, child_bound, child_include) heapq.heappush(pq, (-child_bound, child)) picked_original [items[k][2] for k, chosen in enumerate(best_include) if chosen] return best_profit, picked_original if __name__ __main__: capacity 10 values [6, 3, 5, 4, 6] weights [2, 2, 6, 5, 4] profit, picks knapsack_branch_bound(capacity, values, weights) print(最优总价值:, profit) print(选择物品下标(0-based):, picks)4.2 测试用例设计与输出解读我设计的测试用例是一个很典型的有迷惑性的数据集物品下标价值重量价值密度0623.01321.52560.8333450.84641.5跑出来的结果最优总价值: 15 选择物品下标(0-based): [0, 1, 4]物品0、1、4的总重量是2248小于容量10总价值是63615。这个解的含义很明确物品2虽然价值5但太重物品3性价比最低最优组合里它们都没入选。4.3 手动推导验证最优性既然分支界定法是个精确算法精确体现在它能证明自己找到的就是最优解。我把这个测试用例的几个关键组合列出来验证物品组合总重量总价值0 1 48150 1 210140 1 39130 28110 46122 41011最高价值确实是15没有其他组合能超过它。分支界定法在搜索过程中会反复计算上界比如根节点bound是16.67但所有无法达到15的分支都会被bound剪掉最终只保留最优路径。这个例子很小你可以用手工验证实际跑大数据时没法手工验证但算法性质保证了只要搜索完优先队列拿到的就是全局最优。这也是它比贪心、启发式方法更让人放心的地方。5. 实战心得浮点精度、内存控制和搜索策略5.1 浮点精度问题上界比较别踩边界calc_bound返回的是float而best_profit是整数。当上界刚好等于best_profit时理论上应该剪枝但浮点运算中可能出现15.000000000000002这种值让本应被剪掉的节点继续入队。大多数情况这只会造成少量额外计算不会影响最终正确性。但当数据量大、剪枝依赖频繁时我习惯在比较里加一个极小偏移量EPS 1e-9 if node.bound - EPS best_profit: continue或者另一种更稳的做法既然物品价值是整数可以用math.ceil(bound)把上界向上取整再与整数比较。向上取整后的上界依然不会比真实最优解小所以剪枝仍然安全。5.2 include列表的深拷贝与内存控制我的代码里每个子节点都通过node.include [False]生成新列表。这保证了节点间数据独立但也带来一个问题节点数量一多列表复制的内存开销不可忽视。实测下来当n到几千、搜索空间大时Python的对象开销加上列表复制内存涨得很快。针对这个问题我给两个方向如果想保留完整的选物记录可以用父节点指针 一位决策信息来代替布尔列表。叶子节点回溯时沿着父指针反推能还原完整的选物路径内存从O(n*节点数)降到O(节点数)。如果只是想快速拿到最优价值不在乎具体选了哪些物品甚至可以不存include。这样省掉列表拷贝代码跑起来会快很多。5.3 FIFO vs 优先队列什么时候用LC什么时候用BFS很多人一开始会把分支界定法和队列绑定直接实现一个FIFO的BFS版本。这种写法没有大问题但搜索顺序是逐层展开的缺乏方向性剪枝效率明显不如LC策略。我试过同一组数据FIFO版本扩展了上千个节点而优先队列版本可能只扩展几百个。差距主要来自best_profit更新的时机LC优先看上界高的节点往往很快就能找到一个很接近最优的可行解后面的界剪枝就会非常猛。不过也有例外。如果上界估计非常宽松、所有节点bound都差不多优先队列的优势就不那么明显反而堆的维护开销拖慢速度。但这种情况在实际背包问题里很少见默认用优先队列基本没错。5.4 更大规模实例的优化扩展方向当n继续增大纯Python的分支界定会逐渐逼近极限。在把这套逻辑移植到生产环境时我从几个方向做过优化效果都不错初始下界优化先用贪心法跑一个可行解作为best_profit的初始值。best_profit越大剪枝发生得越早整个搜索过程会显著缩短。并行扩展优先队列本身不容易并行化但可以把上界最高的几个节点分发给多线程/多进程各自搜索最后合并结果。需要注意同步best_profit否则剪枝会不安全。分支定界 割平面工业级整数规划求解器里的branch and cut是分支界定法的进阶版。它在分支之外还会动态添加约束来收紧上界每轮剪枝都变得更狠。如果哪天你面对的问题规模再上几个量级可以往这个方向探索。我后来把这段逻辑移植到Java和Go各写了一遍核心思路完全不变只是把Node和优先队列换了下写法。做这种组合优化问题最值钱的不是调代码细节而是先把分支、定界、剪枝这三个决策想清楚。你把上界估计做得越紧后面搜索越省事你把best_profit初始值喂得越好剪枝效果越显著。希望这篇把原理和代码都摊开的文章能帮你少踩几个我当年踩过的坑。