1. 问题引入从集装箱装船说起最近在复盘算法设计思想时又翻到了回溯法这个老朋友。回溯法听起来有点抽象但它的应用场景其实非常具体比如经典的“装载问题”。想象一下你面前有一艘货轮它的最大载重量是C。现在有一批集装箱要装船每个集装箱都有各自的重量。我们的目标很简单在不超过轮船最大载重的前提下尽可能多地把集装箱装上去让轮船的载重量最大化。这听起来像是个简单的“往背包里塞东西”的问题但一旦集装箱数量多起来比如有几十上百个靠人脑去一个个试组合就完全不现实了。这就是计算机算法大显身手的地方而回溯法正是解决这类组合优化问题的一把利器。装载问题可以看作是0-1背包问题的一个特例或者说是子集和问题的一个变种。它的核心是决策对于每一个集装箱只有两种选择——装船选择1或者不装船选择0。我们需要从所有可能的2^n种选择组合中n是集装箱数量找出那个总重量最接近C但又不超过C的组合。暴力枚举所有2^n种可能性在n稍大时比如n30就变成了天文数字计算时间无法接受。因此我们需要更聪明的搜索策略回溯法通过“试探”和“回退”的机制系统地遍历解空间同时利用“剪枝”技巧抛弃大量明显不可能成为最优解的搜索路径从而极大地提高了效率。2. 回溯法核心思想系统性的试探与回退在深入装载问题之前有必要把回溯法的“内功心法”捋清楚。很多人容易把回溯、递归、深度优先搜索DFS这几个概念混淆。简单来说递归是一种编程技巧函数自己调用自己DFS是一种遍历图或树的策略强调“一条路走到黑”而回溯法是一种算法设计思想它通常用递归来实现并以DFS的方式遍历解空间树但其精髓在于“回溯”这个动作——当发现当前路径不可能导出有效解时就撤销上一步或几步的选择退回到之前的状态尝试其他可能性。回溯法解决问题的过程就像是在走一个巨大的迷宫。我们每到一个岔路口对应做一个决策比如是否装入当前集装箱就选择一条路走下去。边走边判断如果发现这条路前面堵死了当前部分解已经不可能满足约束条件比如总重量已超载或者即使走到头也不是我们想要的最优解通过上界函数预估那我们绝不会傻乎乎地继续走到黑而是立刻掉头回到上一个岔路口选择另一条路继续探索。这种“掉头”就是回溯。对于装载问题这个“迷宫”就是一棵高度为n1的二叉树我们称之为解空间树。树的第i层代表对第i个集装箱做出的决策装或不装每个节点记录了从根节点到该节点路径上所做的所有决策导致的当前总重量。回溯算法从根节点尚未处理任何集装箱开始以深度优先的方式遍历这棵树。在每一个节点它先尝试“装”这个分支左子树递归深入返回后再尝试“不装”这个分支右子树。关键在于在深入任何一个分支之前它需要进行“剪枝”判断避免进入无效的子树从而节省大量时间。3. 装载问题的回溯法求解框架现在我们把回溯法的思想套到装载问题上。假设有n个集装箱其重量分别为w[1], w[2], ..., w[n]轮船的载重量上限是C。我们的目标是找到一个0-1向量x[1..n]x[i]1表示装0表示不装使得 sum(w[i]*x[i]) 最大化且不超过C。3.1 算法状态与递归函数设计我们设计一个递归函数Backtrack(i)其中参数i表示当前正在决策第i个集装箱。算法需要维护几个关键状态cw当前已装入轮船的集装箱总重量current weight。bestw目前搜索到的、满足不超过载重C的最佳总重量。bestx记录达到bestw时对应的装载方案一个0-1数组。r剩余未考虑集装箱的总重量。这是一个非常重要的辅助变量用于后续的剪枝优化。递归的进程可以这样理解递归边界当i n时说明已经对所有n个集装箱做出了决策得到了一个完整的装载方案。此时如果当前重量cw比之前记录的最佳重量bestw更优即更大则更新bestw和bestx。递归体搜索过程对于第i个集装箱我们有两种选择。选择装入搜索左子树首先判断约束条件cw w[i] C。如果满足说明可以尝试装入。那么我们更新状态cw w[i]。然后递归调用Backtrack(i1)去处理下一个集装箱。当这个递归调用返回时意味着以“装入第i个集装箱”为前提的所有后续可能性都已经探索完毕。此时必须进行回溯cw - w[i]即撤销装入第i个集装箱的操作恢复到决策之前的状态以便尝试另一种选择。选择不装入搜索右子树直接递归调用Backtrack(i1)。由于不装入不会改变当前重量cw所以这里没有状态更新和回溯或者说cw 0和cw - 0。这个框架已经是一个正确的回溯算法它会遍历所有可行的装载方案总重量不超过C的并记录最优解。但是它的效率依然不高等同于一个受限的暴力枚举。接下来我们要引入回溯法的灵魂——剪枝。3.2 关键优化上界函数与剪枝策略无剪枝的回溯就像在迷宫里盲目乱撞而剪枝则像是一张地图提前告诉我们哪些岔路没必要进。对于最大化问题我们使用一个上界函数来预估从当前节点继续搜索下去所能达到的最大可能重量。如果这个“可能的最大值”都比当前记录的最佳值bestw还要小或相等那么这条路径就没有继续搜索的必要了可以直接剪掉。在装载问题中一个简单而有效的上界函数是cw r。其中cw是当前已装重量r是剩余所有未考虑集装箱的总重量。cw r的含义是假设后面所有的集装箱都能装上去这显然是最乐观的估计最终能达到的总重量。这个值是当前搜索路径可能达到的重量上界。剪枝条件如果cw r bestw那么即使把后面所有箱子都装上总重量也不会超过当前已知的最优解bestw。因此以当前节点为根的子树中不可能产生比bestw更好的解整个子树都可以被剪掉无需继续递归搜索。这个剪枝条件应该加在哪里它应该在尝试两种选择装或不装之前进行判断。因为无论对第i个集装箱做什么选择后续搜索的上界都是cw r注意在判断时r包含了第i个集装箱的重量。如果当前上界已经不够好那么对于第i个集装箱的两种选择都可以不用尝试了直接返回上一层。具体到算法中在递归函数Backtrack(i)的开头我们加入判断if (cw r bestw) return; // 剪枝然后在尝试“装入”分支前我们判断约束条件cw w[i] C在尝试“不装入”分支前实际上没有约束条件需要判断不装永远不会超载。但注意在进入“不装”分支前r的值需要减去当前集装箱的重量w[i]因为当前集装箱即将被考虑虽然选择不装它应该从“剩余重量”中移除。这个r的更新和恢复也是回溯的一部分。3.3 算法流程与代码骨架结合以上所有点我们可以勾勒出算法的大致流程。为了进一步提升效率我们还可以在搜索前对集装箱按重量从大到小排序。这是一种启发式策略优先考虑重量大的集装箱有助于让cw快速增长从而使得上界cw r更容易触发剪枝条件提前剪掉更多分支。下面是一个清晰的算法步骤描述初始化读入集装箱重量数组w[1..n]和载重量C。对w数组进行非递增排序可选但强烈推荐。初始化cw 0,bestw 0,r sum(w[1..n])。调用回溯从第一个集装箱开始调用Backtrack(1)。输出结果回溯结束后bestw即为最大可装载重量bestx记录了对应的装载方案。递归函数Backtrack(i)的伪代码描述如下// 全局或引用变量n, C, w[], cw, bestw, bestx[], r void Backtrack(int i) { // 递归边界已处理完所有集装箱 if (i n) { if (cw bestw) { bestw cw; 记录当前方案到 bestx; // 需要遍历x[1..i-1] } return; } // 更新剩余重量减去当前正在考虑的集装箱 r - w[i]; // 剪枝即使后面全装也无法超越当前最优解 if (cw r bestw) { r w[i]; // 恢复剩余重量因为要返回了 return; } // 搜索左子树尝试装入第 i 个集装箱 if (cw w[i] C) { // 约束条件判断 cw w[i]; x[i] 1; // 记录选择 Backtrack(i 1); cw - w[i]; // 回溯撤销选择 // x[i] 在搜索右子树时会被覆盖无需显式回溯 } // 搜索右子树尝试不装入第 i 个集装箱 // 注意此时 cw 未变r 已经减去了 w[i] // 在进入右子树前理论上可以再判断一次 cw r bestw但通常左子树返回后cw已恢复此时判断与函数开头判断等价 Backtrack(i 1); // 回溯恢复剩余重量 r w[i]; }4. 一个完整的计算实例与逐步推演理论说得再多不如一个例子来得实在。假设轮船载重量C 10有4个集装箱其重量分别为w [5, 2, 1, 4]。为了应用剪枝我们先按重量非递增排序此例中已是非递增顺序5, 4, 2, 1。初始状态cw0,bestw0,r542112。我们手动模拟一下回溯搜索树的关键步骤重点关注剪枝是如何发生的。解空间树是一棵深度为5n1的二叉树。根节点 (i1, cw0, r12)处理第一个集装箱重5。上界cwr12 bestw(0)继续。左子树装5cw55 C(10)可行。进入状态cw5, r12-57。节点 (i2, cw5, r7)。处理第二个集装箱重4。上界5712 bestw(0)继续。左子树装4549 10可行。进入cw9, r7-43。节点 (i3, cw9, r3)。处理第三个集装箱重2。上界9312 bestw(0)继续。左子树装29211 10超载此路不通直接返回不继续递归。右子树不装2进入cw9, r3-21。节点 (i4, cw9, r1)。处理第四个集装箱重1。上界9110 bestw(0)继续。左子树装19110 10可行。进入cw10, r1-10。节点 (i5)。in到达叶子节点。更新最优解bestw 10记录方案[装装不装装]即[1,1,0,1]。返回。右子树不装1进入cw9, r0。节点 (i5)。到达叶子节点。当前cw9小于bestw(10)不更新。返回。回溯恢复rr从1加回2变为3。回溯cw从9减回5不对注意顺序。在节点(i3)的右子树调用返回后函数结束会执行最后的r w[3]即r325。然后返回到节点(i2)。右子树不装4在节点(i2)尝试完左子树后cw已回溯为5r已恢复为7。现在尝试不装4。进入cw5, r7-43。节点 (i3, cw5, r3)。处理第三个集装箱重2。上界538。注意此时bestw已经是10了。8 bestw(10)触发剪枝整个以“装5不装4”为前缀的子树全部被跳过无需继续探索。这节省了探索“装5不装4装/不装2装/不装1”这整个子树的时间。回溯恢复rr325这里因为触发了剪枝直接返回并没有执行到对右子树的递归调用但r在函数开头被减去了w[3]即2所以需要在返回前恢复。在我们的伪代码中剪枝分支在返回前会执行r w[i]。回溯在节点(i2)的右子树调用返回后恢复rr7411不对在节点(i2)的函数末尾会执行r w[2]即r7411。但注意进入节点(i2)时r7是已经减去了w[2]的所以这里加回来r变回进入节点(i2)之前的值即12这里有点绕。关键在于r是一个动态变化的全局量。在进入Backtrack(2)时r是7因为在Backtrack(1)中已经r - w[1]。在Backtrack(2)内部开头r - w[2]变为3。在结束Backtrack(2)返回前执行r w[2]r从3变回7。所以返回到Backtrack(1)时r的值是7。回溯在节点(i1)的左子树调用返回后cw从5减回0。r在Backtrack(1)的函数末尾执行r w[1]从7变回12。右子树不装5现在尝试不装第一个集装箱。进入cw0, r12-57。节点 (i2, cw0, r7)。处理第二个集装箱重4。上界077。此时bestw10。7 bestw(10)触发剪枝整个以“不装5”为根的庞大子树被全部剪掉。搜索提前结束。最终我们只探索了整棵解空间树的一小部分主要是“装5”的那条主干及其部分分支就找到了最优解bestw10方案是装入第1、2、4个集装箱重量5,4,1。通过剪枝我们避免了探索“不装5”的整个半边树以及“装5不装4”的子树搜索效率大大提升。5. 算法性能分析与实战要点回溯法解决装载问题的时间复杂度在最坏情况下仍然是指数级的 O(2^n)因为本质上它还是在遍历一棵二叉树。但是通过有效的剪枝平均情况下的运行时间会远小于最坏情况。剪枝的效果取决于数据特征集装箱重量分布如果重量分布均匀且C相对于总重量较小剪枝会非常有效因为很容易触发cw r bestw。排序启发按重量非递增排序是至关重要的优化。它让重量大的集装箱优先被考虑使得cw能较快增长从而尽早地找到一个较好的bestw。一个好的bestw能更早、更频繁地触发上界剪枝。如果不排序算法可能先探索一堆轻箱子的组合bestw增长缓慢导致剪枝条件迟迟不满足需要探索更多节点。问题规模尽管有剪枝当n非常大例如上百时最坏情况下的计算时间依然不可接受。这时就需要考虑其他算法如动态规划对于整数重量存在伪多项式时间算法或启发式算法、近似算法。在实际编码和面试中有几个细节需要特别注意全局变量与状态恢复cw,bestw,r,bestx通常作为全局变量或引用参数传递。最关键的是在递归调用返回后必须精确地恢复现场cw - w[i],r w[i]这是回溯正确性的保证。忘记恢复状态是初学者最常见的错误。上界函数的准确性我们使用的cw r是一个宽松上界。在某些变种问题中如果存在更紧的上界例如考虑到后面集装箱不能全部装入可以使用更精确的上界函数来增强剪枝能力。记录最优解在更新bestw时必须同步记录当前的装载方案x[1..n]。不能只记录重量否则无法输出具体装了哪些箱子。这需要将当前方案数组x复制到bestx中。迭代加深与可行性剪枝除了最优性剪枝上界剪枝还有简单的可行性剪枝在尝试装入一个箱子时如果cw w[i] C则这个“装入”分支根本不可行直接跳过。我们在代码中通过if (cw w[i] C)实现了这一点。装载问题是理解回溯法思想的一个绝佳样板。它清晰地展示了如何构建解空间树如何通过深度优先搜索遍历以及如何利用约束条件和上界函数进行剪枝。掌握这个例子就能触类旁通应用到其他类似的问题上比如0-1背包、子集和、图着色、n皇后等问题。其核心模式是一致的定义状态深度优先搜索在每一步判断约束和上界回溯时恢复状态。多动手模拟几遍搜索过程对这种“试探-回溯-剪枝”的节奏就会有更深刻的肌肉记忆。