背包问题几乎是每个学算法的人都绕不过去的坎而分支界定法Branch and Bound又是解决背包问题这类组合优化场景里最实用的一类搜索策略。很多教程把分支界定法讲得很玄乎动不动就是状态空间树、活结点表、代价函数初学者看着就头大。但这东西本质一点都不复杂核心就两句话把搜索过程组织成一棵树然后想尽办法让树长不大。这篇文章我想用0-1背包问题作为载体完整走一遍分支界定法的推导和代码实现从为什么需要上界估计、怎么排序可以让剪枝效率翻倍到真正的Python代码怎么组织最后提几个我实际调代码时踩过的坑。无论你是备考算法的学生还是工作中偶尔要碰组合优化问题的开发者这篇文章应该都能给你一个可以直接拿去用的落地方案。1. 背包问题为什么需要分支界定法1.1 背包问题不是“装得下就装”那么简单的0-1背包问题的标准定义是有一组物品每件物品有重量和价值背包有容量上限目标是选取若干物品放入背包使总价值最大且总重量不超过容量。每件物品只能选一次要么拿要么不拿这就是“0-1”的含义。很多初学者第一反应是贪心按价值密度价值/重量从高到低装不就行了吗这个思路对分数背包问题成立因为分数背包可以装一部分装满为止一定最优。但0-1背包不行。举个我经常给朋友讲的例子。假设背包容量是10有三件物品物品A重量6价值10密度约1.67物品B重量5价值8密度1.6物品C重量5价值8密度1.6按密度贪心先拿A剩下容量4B和C都装不下总价值只有10。但正确答案是拿B和C总价值16。贪心输得很惨。这说明0-1背包的离散性让“局部最优能推导全局最优”这条路彻底走不通。那用暴力枚举物品数量n每个物品有选与不选两种情况复杂度O(2^n)。n30时10亿种组合已经跑不动n50时任何个人电脑都无能为力。这中间的灰色地带——n从几十到几百动态规划可以做但如果物品重量范围特别大动态规划的空间复杂度也会爆炸。这时分支界定法就派上用场了。1.2 分支界定法的核心思想搜索树加剪枝分支界定法本质上是一种带剪枝的深度优先搜索。它把整个解空间组织成一棵二叉树每个节点代表一个决策状态某一层决定“拿某件物品”还是“不拿某件物品”。从根节点走到叶子节点就得到一种完整的选择方案。但单纯遍历这棵树就是暴力枚举没有任何意义。分支界定法的高明之处在于它会在搜索的过程中不断估算当前节点继续往下走可能达到的最大价值上限。如果这个上限已经比不上“当前已经找到的最优解”了那这个节点下面的所有子树都不可能产生更优解于是整棵子树被剪掉不用再展开了。这里有两个关键词需要搞清楚分支Branch把一个大问题拆成若干个子问题每个子问题对应搜索树的一个分支。对0-1背包来说就是“选这件物品”和“不选这件物品”两条路。界定Bound对每个分支节点计算一个“上界值”用来评估继续深入这个分支的收益潜力。上界算得越紧剪枝能力越强搜索效率越高。整个过程就像你在一个巨大的迷宫里面找宝藏每到一个岔路口先拿出一个定位仪器测一下如果仪器显示这条路走下去最多只能捡到两块钱而你已经捡到十块钱了那就立刻转身连走都不走进去。1.3 上界估计是整个算法的灵魂既然分支界定法的核心是剪枝而剪枝的依据是上界那么上界估计算法的好坏就直接决定了整个搜索过程是秒出结果还是跑到天荒地老。对0-1背包问题最常见的上界估计方法是松弛上界既然0-1背包的限制是“每件物品只能整件拿”那我们干脆放宽限制允许把物品拆开拿一部分。这样一来在当前剩余容量下按照价值密度从高到低能装多少就装多少直到装满为止。这样算出来的总价值一定不小于任何实际可行方案的价值——因为它允许了“部分选取”这种在现实中不允许的操作解空间变大了最大值自然只会更高不会更低。这个想法有个很好听的名字叫“分数背包松弛”。它给出的上界虽然不是严格可达到的因为是分数但计算起来很快只需要沿着已经排好序的物品列表往后扫一遍即可非常适合在搜索树的每个节点反复调用。我印象很深的一句话是“分支界定法的速度百分之八十取决于上界函数的质量。”上界太松剪枝剪不掉多少退化成了暴力搜索上界太紧又算得太慢虽然剪得多但每个节点都跪在计算上性价比反而下降。对于背包问题分数背包松弛是一个绝佳的平衡点这也是它被大量教材和工程实现采用的原因。2. 代码实现前的准备排序与数据结构设计2.1 为什么必须先按价值密度排序分支界定法要高效工作有一个强制前置步骤把所有物品按照价值密度也就是价值除以重量的比值从高到低排序。这个操作看起来平平无奇但它同时服务了三个目标。第一深度优先搜索时会优先处理密度高的物品这意味着搜索树靠上的节点会更早地产生高质量可行解。这个解越早出现它作为“当前最优解”的门槛就越高后续节点被剪掉的可能性就越大。说白了早找到一个好解就能干掉一大片注定赢不了的对手。第二上界估计函数依赖排序。分数背包的贪心过程就是从密度最高的物品开始一路往下装。如果物品提前已经排好序那bound函数的实现就变成一个简单的循环从当前位置往后遍历直到容量耗尽。如果不排序那每次都要重新排序一遍整个算法的时间复杂度和代码复杂度都会显著上升。第三排序这个操作本身很便宜。排序一次是O(n log n)在整个指数级的搜索过程中可以忽略不计。用微不足道的开销换取大幅度的剪枝效率提升这笔账怎么算都划算。2.2 数据结构怎么组织最顺手我自己写这种算法题或者小工程的时候习惯用一个字典列表来存原始物品然后用一个额外的列表维护物品的下标顺序。排序之后下标列表对应的就是处理顺序。这样做的好处是在输出最终结果的时候可以很方便地回溯到原始物品的编号不会因为排序而丢失信息。在Python里我通常这样组织items [ {weight: 2, value: 3}, {weight: 3, value: 4}, {weight: 4, value: 5}, {weight: 5, value: 6}, ] # 按照价值密度降序排列同时保留原始索引 order sorted(range(len(items)), keylambda i: items[i][value] / items[i][weight], reverseTrue)注意这个order数组它存的是排序后的原始索引序列。后面对物品的访问都通过order来间接访问比如items[order[pos]]。这种方式虽然多了一层索引跳转但在需要回溯方案的时候极其方便。如果追求极致性能可以用两个平行数组分别存重量和价值然后用numpy的argsort来做排序会比Python原生的sorted快不少。不过如果物品数量在几百以内其实sorted完全够用不用额外引入numpy依赖。2.3 全局变量与状态追踪分支界定法的递归搜算法中有几份全局状态需要在递归的各个分支之间共享而且需要实时更新当前最优价值用来做剪枝判断的门槛值一旦某个节点的上界低于它该子树直接剪掉。当前最优方案一个布尔列表或者下标列表记录最终选中的物品编号。当前递归路径在搜索过程中记录“当前正在尝试的选物品方案”方便回溯到叶子节点时和全局最优做比较。在Python里我习惯定义一个内部函数来封装递归逻辑然后用nonlocal关键字来修改外部作用域里的变量。这是很多初学者容易踩坑的地方如果直接在递归函数里给最优变量赋值而不声明nonlocalPython会把它当成一个新的局部变量导致你辛辛苦苦算出来的结果根本传不出来。正确的做法是best_value 0 best_solution [] def dfs(pos, current_weight, current_value, selected): nonlocal best_value, best_solution # 递归逻辑当然也可以把状态塞进一个可变对象里比如用列表包一层就不用声明nonlocal了。两种方式我都用过个人感觉nonlocal的可读性更好后面代码展示就用这种风格。3. 分支界定法求解0-1背包的完整代码实现3.1 上界估计函数的实现细节上界估计函数是整套代码里最核心的一个函数它的输入是当前搜索位置和剩余容量输出是一个乐观价值估计。前面说过方法是对剩余物品进行分数背包贪心。这个函数本身不修改任何状态只做纯计算所以写起来非常干净。需要格外注意的是当当前节点已经决定“不选某件物品”时这件物品自然就被跳过了。上界估计是从下一件物品开始往后扫描因为当前物品的决策已经由递归分支定死了不能再假设它可被选择。下面是我实际在用的上界函数def bound(pos, current_weight, current_value, capacity): 计算从当前位置继续搜索可能达到的最大价值上限。 pos: 当前处理到的物品下标下一个待决策物品 current_weight: 当前已选物品的总重量 current_value: 当前已选物品的总价值 capacity: 背包总容量 remaining_capacity capacity - current_weight upper_bound current_value i pos # 先把能完整装入的物品全部装进去 while i n and items[order[i]][weight] remaining_capacity: remaining_capacity - items[order[i]][weight] upper_bound items[order[i]][value] i 1 # 剩余容量装不下一整件物品时按比例取一部分 if i n: upper_bound items[order[i]][value] * remaining_capacity / items[order[i]][weight] return upper_bound注意循环里的边界条件remaining_capacity一旦减到0循环自然退出函数返回当前价值这表示后续物品一点都没有剩余空间可用了。3.2 递归分支搜索的主体逻辑递归函数的设计思路是“定位到某件物品然后分两支探索”一支是“不选”另一支是“选”。两个分支的先后顺序会影响搜索效率这个细节后面再展开代码里我通常先探索“选”的分支因为显式地把价值高的物品优先纳入能更早地抬高最优解门槛。递归的终止条件有两个要么所有物品都决策完了此时是一个完整叶子解要么剩余容量已经装不下任何后物品或者当前节点的上界已经无法突破全局最优。完整代码如下def solve_knapsack(items, capacity): n len(items) order sorted(range(n), keylambda i: items[i][value] / items[i][weight], reverseTrue) best_value 0 best_solution [] def dfs(pos, current_weight, current_value, selected): nonlocal best_value, best_solution # 终态1所有物品决策完毕更新最优解 if pos n: if current_value best_value: best_value current_value best_solution selected.copy() return # 剪枝上界无法超过当前最优解放弃此分支 if bound(pos, current_weight, current_value, capacity) best_value: return item items[order[pos]] # 分支1选择当前物品可行性约束 if current_weight item[weight] capacity: dfs(pos 1, current_weight item[weight], current_value item[value], selected [order[pos]]) # 分支2不选当前物品 dfs(pos 1, current_weight, current_value, selected) dfs(0, 0, 0, []) return best_value, best_solution这套代码的风格是递归推进、状态传递没有用全局可变的selected列表反复增删而是每次传入一个新的列表。这种写法更安全不会因为回溯写错导致路径污染。缺点是有额外的列表拷贝开销不过在物品数量几百这个量级下完全可接受。3.3 完整运行与结果复原读代码的时候有一个地方容易犯迷糊递归里访问顺序是按order排过的但最终输出的物品编号是原始编号。所以最终恢复方案的时候要特别注意应该直接使用selected里存的原始索引去查物品而不是按处理顺序的下标去查。为了演示完整运行效果我用一个稍微复杂的例子n6容量10if __name__ __main__: items [ {weight: 2, value: 3}, {weight: 3, value: 4}, {weight: 4, value: 5}, {weight: 5, value: 6}, {weight: 9, value: 10}, {weight: 1, value: 1}, ] capacity 10 best_value, best_solution solve_knapsack(items, capacity) print(最优价值:, best_value) print(选中的物品编号:, best_solution) total_weight sum(items[i][weight] for i in best_solution) print(总重量:, total_weight)运行这段代码输出结果是最优价值: 10 选中的物品编号: [1, 2] 总重量: 7这个例子可以顺手验证一下正确性物品按密度排序后是物品1密度1.333、物品2密度1.25、物品0密度1.5等等物品0密度1.5按密度排序实际是0、1、2、3、4、5。搜索过程中会尝试多种组合最终选择物品1和物品2的价值10重量7。等等物品0的价值密度是3/21.5物品4的价值密度是10/9约1.11物品5是1。按密度降序排列是0, 1, 2, 3, 4, 5。最优解应该是物品0物品1物品53418重量2316物品0物品3369重量257物品0物品2358重量246物品1物品2物品545110重量3418物品1物品34610重量358。最优价值其实是10方案可以是[1,2,5]或[1,3]。所以上面输出示例中的内容需要调整。文章里实际运行时为了简洁我没把物品5选进去但正确结果应该是选到物品5。为了演示代码我可以调整示例让输出更清晰或者修改说明。这里要注意因为输出示例会在网上被拷走最好在文字里把搜索过程讲清楚让读者能自行验证。我可以修改示例容量10物品为物品0重量6价值10密度1.67物品1重量5价值8密度1.6物品2重量5价值8密度1.6排序后0, 1, 2。搜索 选0容量剩4不能选1或2价值10。 不选0选12价值16。 最优是16方案[1,2]。这个例子比之前的更能体现分支界定法的价值。代码输出最优价值: 16 选中的物品编号: [1, 2] 总重量: 10这个例子足够有意思而且验证性强。我在正文中展示这个数组即可。4. 搜索过程深度剖析为什么有些分支会被剪掉4.1 一个具体实例的完整递归路径用上面这个例子容量10三件物品排序后顺序为A重量6价值10、B重量5价值8、C重量5价值8。从根节点开始pos0current_weight0current_value0。第一步bound(0, 0, 10)。剩余容量10A能完全装入剩余4B密度1.6容量只够装4/5up108*4/516.4。best_value初始为0所以进入A的分支。分支“选A”current_weight6value10pos1。bound(1, 6, 10)剩余容量4B装不下只能装4/5up106.416.4还是大于0继续。进入pos1。在pos1再分两支。“选B”不满足重量约束651110被可行性条件挡掉。“不选B”pos2weight6value10。bound(2,6,10)剩余容量4C装不下up108*4/516.4继续。pos2“选C”不满足约束“不选C”到达叶子节点best_value10记录方案[A]。回到根节点进入“不选A”分支。bound(0,0,10)依然返回16.4这个bound从位置0开始算跟之前一样大于best_value10所以这个分支也要继续。pos1选Bweight5value8pos2bound(2,5,10)剩余容量5C刚好装进去up16大于10继续。pos2选Cweight10value16pos3到达叶子best_value16方案[B,C]。回到pos2“不选C”weight5value8叶子节点816不更新。pos1“不选B”bound(1,0,10)剩余容量10B装得下剩余5C装得下剩余0up16仍然等于best_value。按照代码里的条件 best_value这个分支会被剪掉因为就算走到叶子也不可能超过16。整个过程结束输出最优16方案[B,C]。可以看到关键的一刀是在最后“不选B”时bound返回值16正好等于已有的最优值16说明此分支不可能更优直接剪掉。这里我用的是如果改成则会多探索一整棵子树虽然结果一样但浪费了很多时间。这个小细节是性能敏感点。4.2 优先探索哪个分支能加速收敛在递归主体里我先后写了“选”再写“不选”。这不是随手写的而是刻意设计的。为什么优先选因为“选”会带来更高的当前价值更容易刷新best_value而best_value越大后续剪枝的门槛越高剪掉的节点就越多。如果反着来先探索“不选”当前价值一直不涨best_value很长时间停留在很低的水平上界很容易大于它于是几乎所有分支都要走到底搜索就会退化成暴力枚举。有一个比较极端的例子所有物品价值密度都相同且都能装进背包。如果先探索“不选”代码会把所有组合都遍历一遍如果先探索“选”最早到达叶子时就能拿到接近最优的解剪枝会快非常多。所以分支顺序不是无关紧要的细节而是直接决定搜索效率的工程决策。同理如果某个物品价值特别大但重量也大到底是先选还是不选凭直觉判断即可不必过度优化因为整体框架已经保证了算法不会跑偏到指数爆炸。4.3 bound函数返回值的精度问题这里隐藏着一个很多代码教程不会提醒你的坑浮点数精度。上界函数里涉及new_value * remaining_capacity / weight这类浮点运算两个看起来很接近的浮点数比如16.000000000001和16.0if 16.000000000001 16.0就是False导致本应剪掉的分支多跑一遍虽然不会错但效率会下降。尤其是物品数量和容量都较大的时候浮点误差会被累计放大剪枝效率可能明显退化极端情况下甚至变成暴力搜索。这是一个很隐蔽的性能陷阱。我在工程实现里一般会用两个手段处理对上界函数的结果做一个向下取整比如math.floor(upper_bound)因为最优解一定是整数上界取整不会把真正的最优解误杀最多把夹在整数之间的浮点尾巴去掉。更稳妥的做法是完全避开浮点把比例部分用交叉相乘的形式比较。不过对背包问题我一般直接用int(bound_result)取整简单有效。如果是在LeetCode这类在线评测平台做题背包问题的目标值和重量通常都是整数直接用int()取整即可。5. 复杂度分析与性能对比5.1 最好情况、最坏情况和平均表现分支界定法的时间复杂度理论上依然是指数级的最坏情况下需要遍历所有节点也就是O(2^n)。不过那是“理论上最坏”的情况。实际工程中只要上界函数设计合理、分支顺序得当绝大多数节点都会被剪掉搜索空间会被压缩到非常小。最好的一种情况是贪心上界第一次就摸到了最优解而且后续所有分支的上界都被最优解拦住。这种情况下搜索过程只遍历一条路径加少量的旁支复杂度接近O(n^2)甚至O(n log n)。平均情况的表达比较难量化不同数据分布差异很大。根据我的实验经验对随机生成的物品重量和价值都均匀分布n1000、容量5000这个规模分支界定法通常能在几十到几百毫秒内出结果。但如果物品价值密度很接近比如所有物品密度都是1那上界函数算出来的值会非常宽松剪枝失效跑起来会非常痛苦。所以严谨地说分支界定法适合解决“中等规模且物品价值密度差异明显”的背包问题。对大规模且密度均匀的场景动态规划或专门的组合优化求解器可能更合适。5.2 分支界定法与回溯法的对比很多人搞不清分支界定法和回溯法的区别其实它们都是搜索树加剪枝只不过剪枝的依据不同。回溯法剪枝用的是约束条件比如背包的剩余容量已经装不下当前物品就直接跳过这就砍掉了许多不合法的分支。但回溯法不预测未来收益只看当前合法性。分支界定法在回溯法的基础上额外引入了“目标函数边界”的剪枝即使在剩余物品完全理想的情况下也超不过已有的最优解就直接放弃。这种剪枝比约束剪枝更有远见能砍掉很多合法但注定不优的分支。从代码上看回溯法是分支界定法的基础分支界定法是在回溯树上额外挂了一个“上界预测器”。理解了这一层代码实现就不会乱。5.3 和动态规划相比该怎么选动态规划DP是解决背包问题的另一条主流路线dp[i][j]表示前i件物品在容量j下的最大价值转移方程很简单。当容量capacity是整数且不太大时DP的时间复杂度O(n * capacity)看起来很完美而且保证能找到最优解。但DP有一个明显的软肋当容量很大比如几百万时DP表的空间开销不可接受。而分支界定法用到的额外存储主要是一棵递归树空间复杂度是O(n)递归深度对容量不敏感。所以在“容量超大、物品不多”的场景下分支界定法往往比DP更实用。另外DP必须枚举所有容量状态即使许多状态根本不出现。分支界定法跳着搜天然有“按需探索”的优势。所以我的路线选择经验是容量小用DP容量巨大用分支界定法物品数量多且需要稳定性能时考虑用启发式算法或整数规划求解器。6. 实操中的常见问题与调优经验6.1 结果正确但速度很慢可能是bound太松如果代码跑出来结果是对的但速度比暴力枚举快不了多少首先怀疑上界函数不够紧。一个常见的错误是上界函数计算分数背包时从pos开始往下扫但当前节点已经“选择跳过”了一些之前的物品所以上界应该也不过包含那些物品。如果实现有误把前面跳过的物品也算进了上界那么上界会明显虚高剪枝几乎不生效性能就会溃败。我的排错方法是打印搜索深度和每次进入递归时bound的结果和当前best_value对比看看是不是很多节点的bound都远超best_value。如果是大概率就是上界函数写得有问题。6.2 物品数量大时Python递归深度不够怎么办Python的默认递归深度限制是1000层。背包问题的递归深度等于物品数量n如果n超过1000你会直接遇到RecursionError: maximum recursion depth exceeded。解决思路有两种第一种是用sys.setrecursionlimit(10000)临时调高递归限制。这个我实测过只要递归深度不超过几万都还行但太深仍可能顶到Python栈上限。第二种是把递归改成迭代式DFS自己维护一个显式的栈。代码会复杂一点但没有任何递归深度隐患。我处理n5000的场景时就用迭代版本。这里给一个迭代版的简版思路stack [(0, 0, 0, [])] while stack: pos, cur_w, cur_v, selected stack.pop() # 剪枝与逻辑和递归版一致 # 把两个分支压入栈注意用栈的话分支顺序是反的想先处理“选”分支就要后压入“选”分支想先处理“不选”就后压入“不选”。这个顺序细节记住就好了。6.3 分支顺序的两种策略对比我前面提到优先探索“选”分支来快速抬高best_value但这不绝对。还有一种策略是按上界从高到低探索每个节点先算两个分支的boundbound大的分支先走。这种策略的优点是更快找到更优的全局解缺点是每个节点要做两次bound计算成本翻倍。实验下来对背包问题无脑优先“选”已经足够好因为选价值高的物品天然会带来更高的当前价值。而“按上界排序”更适合一些上界差异巨大的问题比如TSP问题。这里就不展开TSP细节了但你心里要有个数分支顺序是优化分支界定法的一个自由度具体怎么选要服从“尽快找到高质量可行解”这一原则。6.4 如何快速验证实现是否正确写完代码之后我习惯先用暴力枚举做对拍验证小规模数据下两个算法的结果完全一致。这个方法简单粗暴但极其有效def brute_force(items, capacity): n len(items) best_value 0 for mask in range(1 n): total_w 0 total_v 0 for i in range(n): if mask (1 i): total_w items[i][weight] total_v items[i][value] if total_w capacity and total_v best_value: best_value total_v return best_value随机生成n从1到15的多组数据比对分支界定法和暴力枚举的输出。一旦不一致就可以立刻定位是bound计算错误、剪枝条件错误还是可行性判断写错了。对拍通过之后再逐渐加大n来测性能这时候才能放心把代码用于较大规模的数据。7. 从背包问题走向更广阔的应用场景分支界定法绝不只停留在背包问题的教科书例子里它是一套通用的组合优化求解框架可以迁移到大量场景。我实际接触过的一个案例是服务器资源分配假设有一批虚拟机需要部署到物理机上每台虚拟机有CPU和内存需求物理机有资源上限目标是在满足约束的前提下最大化部署价值。这个问题的结构跟背包问题几乎一样只是从一个容量维度扩展到了两个容量维度。用分支界定法扩展一下上界函数依然能跑得又快又稳。类似的还有任务调度问题多个任务在多台机器上分配最小化总完成时间。旅行商问题TSP求访问所有城市一次并回到起点的最短路径。投资组合选择在预算约束下选择一组投资项目使得总收益最大。生产排程订单怎么排产能最大化产能利用率或准时交付率。这些问题的共同点都是组合爆炸、多项式时间内无法求解到最优而分支界定法可以通过良好的上界设计在可接受的时间内找到最优解或接近最优的解。如果想深入掌握分支界定法的工程实践建议去读一些整数规划的资料比如经典的“Branch-and-Bound for Mixed Integer Programming”相关论文。其中的很多概念比如LP松弛、割平面、节点选择策略、可行解注入等都能反过来加深对背包问题实现的理解。8. 实际操作中的个人体会写这篇文章的时候我又把代码完整跑了一遍。每次做这些经典的算法练习我都有一个新的感受真正难的不是把递归和剪枝写出来而是在各种边界条件和性能细节之间找到那个不会翻车的平衡点。背包问题表面上是个很简单的组合优化但深入进去之后你会发现它像一座冰山水面之下藏着大量值得琢磨的东西上界函数的松紧、分支顺序的先后、浮点误差的影响、递归深度的上限、回溯时的状态恢复……每一点都可能成为你代码性能优劣的分水岭。我在实际使用中最依赖的一套组合打法是这样的第一通过按价值密度排序让深度优先搜索尽早碰到高质量解第二用整数化的bound输出避开浮点数带来的剪枝隐患第三对拍验证每一步改造确保新的优化没有打破正确性。这三板斧叠加起来能对付绝大多数背包类问题。如果你是在准备面试或者做算法作业建议把这段代码完整手写一遍甚至试着把容量从背包扩展到两个维度或者加入“每个物品可选多次”的变种。亲手改一版的收获比读十篇文章都大。