同一道题五种写法：最快的那个，答案是错的

这是整组文章的第四篇，也是最核心的一篇。

前三篇讲体系和分析，这一篇讲设计——怎么想出一个算法。

我不打算给你五个模板让你背。我想给你看一件事：同一道题，五种解法，复杂度和正确性的关系不是你想的那样。

一、先讲那个「最快的」

题目很朴素，叫 0/1 背包：

有一个背包，容量 C。有 n 件物品，每件有重量 w 和价值 v。 每件物品要么整个装进去，要么不装（不能切开）。 问：怎么装，总价值最大？

现在假设有人给你一个方案：

先把物品按「性价比」排序（价值 ÷ 重量），从高到低往包里塞，塞不下就跳过，继续看下一个。

这个办法叫贪心法。它有多快？排序 O(n log n)，一趟扫描 O(n)，总共 O(n log n)。

比起暴力枚举所有子集（2ⁿ），这是天壤之别。

但它是错的。

教材里原话是（《算法设计与分析（微课版）》印刷 128）：

0/1 背包问题不能用贪心法求解，因为物品不允许分割，无法保证最终能将背包装满，部分闲置的背包容量降低了背包的单位重量价值。

翻译一下：你按性价比塞，塞到最后会剩一点空间装不下任何东西——那点空间浪费了。而浪费掉的空间，本来可以换一种装法把它用上。

举个具体例子你就懂了：

背包容量 C = 10
物品 A：重量 6，价值 10   （性价比 1.67）
物品 B：重量 5，价值 9    （性价比 1.80）
物品 C：重量 5，价值 9    （性价比 1.80）

贪心：先塞 B（性价比最高），剩 5，再塞 C，正好装满，总价值 18。 等等，B+C = 10，正好装满。这个例子贪心赢了。

换一个：

背包容量 C = 10
物品 A：重量 6，价值 12   （性价比 2.00）
物品 B：重量 5，价值 9    （性价比 1.80）
物品 C：重量 5，价值 9    （性价比 1.80）

贪心：先塞 A（性价比最高），剩 4，B 和 C 都装不下，总价值 12。 最优：B + C = 10，总价值 18。

贪心少了 6，也就是少了三分之一。

这就是问题所在：贪心做了局部最优的选择，掉进了全局的坑里。

更快，但是错的。这两件事没有必然联系——快不等于对。

二、五种写法，同一道题

这道题在教材里出现了五次，分别用五种方法解（页码见文末）。把它们摆在一起看，才有意思：

注意这张表的形状：

• 最快的是错的（贪心）
• 最慢的是对的，但没用（蛮力）
• 能用的两个都靠同一件事：动态规划和限界剪枝，都是靠**「不重复算已经算过的」**把 2ⁿ 压下来

这不是巧合。这是整个算法设计的核心思想。

三、五种写法，逐个看它在干什么

1. 蛮力法：不是「笨办法」，是「基线」

很多人看不起蛮力法。但蛮力法有个别的办法给不了的东西：它是正确性的基线。

任何聪明的算法，都要和蛮力的结果对一遍——尤其是你怀疑贪心是不是错了的时候。

它的代价也很清楚：n 件物品有 2ⁿ 个子集，这是问题的下界，不是算法写得烂。就算你有无限快的机器，枚举也得枚举 2ⁿ 次。

蛮力法的价值不在于用，在于「知道答案应该是什么」。

2. 贪心法：什么时候能用，什么时候必错

贪心的判据只有一条：

局部最优能不能推出全局最优？

能，贪心成立，而且往往是最快的解法。不能，贪心就是个陷阱，而且它跑得飞快，你很难发现它错了。

哪些问题能：

• 活动安排（选最多的不冲突活动）：按结束时间排序，能选就选 —— ✅
• 最小生成树（Kruskal、Prim）：每次选最小边 —— ✅
• 找零钱（人民币面额）：每次用最大面额 —— ✅
• 单源最短路（Dijkstra，非负权）：每次选最近点 —— ✅

哪些问题不能：

• 0/1 背包 —— ❌ 「部分背包」（物品可切分）却可以，一字之差，性质全变
• 旅行商（TSP） —— ❌ 每次选最近的邻点会走进死胡同
• 图着色（用最少颜色） —— ❌ 按顺序贪心可能多用很多颜色

关键区别在哪？

能贪的问题，通常有「交换论证」：你能证明「最优解里一定包含我这个贪心选择」。 不能贪的问题，通常因为「局部选择会消耗掉全局资源」——像背包的空间，塞了这个就塞不了那个。

3. 动态规划：把「重复计算」消灭掉

这是五种方法里最值钱的一个。

它的核心不是「填表」，是这一句：

同样的问题，只算一次。

蛮力法为什么慢？因为它在重复算同样的子问题。n 件物品，考虑「前 3 件、容量还剩 7」这种情况，会在无数条分支里被算无数遍。

动态规划做的事很简单：把算过的结果存起来，下次直接查。

具体两步：

1. 定义状态：V[i][j] = 前 i 件物品、容量 j 时能拿到的最大价值
2. 转移：对第 i 件物品，要么不装（V[i-1][j]），要么装（V[i-1][j-w[i]] + v[i]），取大的那个

V[i][j] = max( V[i-1][j],                        // 不装第 i 件
               V[i-1][j-w[i]] + v[i] );          // 装第 i 件

复杂度 O(nC) —— 从 2ⁿ 降到 n×C，这是指数级到多项式级的跨越。

但注意那个 C。 C 是背包容量，如果 C = 10⁹，O(nC) 一样跑不动。

动态规划不是「万能提速」，它只是把「指数」换成了「问题规模里的某个数」。这个数太大，照样完蛋。

这就是为什么 0/1 背包是 NP 完全问题——O(nC) 看起来是多项式，但 C 是数值不是位数，所以它是「伪多项式」。

动态规划的两个前提，缺一不可：

1. 最优子结构：大问题的最优解包含小问题的最优解
2. 重叠子问题：不同的路径会走到同样的子问题（不然存了也没用）

4. 回溯法：把所有可能性排成树，然后砍枝

如果问题没有最优子结构（比如「列举所有可行解」），动态规划用不上，就轮到回溯。

思路：把选择过程画成一棵树，深度优先地走。走不通就退回来换一条路。

0/1 背包的树很好画：每层对应一件物品，左分支「装」，右分支「不装」。n 件物品，叶子节点 2ⁿ 个。

回溯的价值全在剪枝：

• 约束剪枝：当前重量已经超过容量 → 这条分支整棵砍掉
• 限界剪枝：当前价值 + 剩下所有物品全装上的价值 < 已知最优解 → 砍掉

第二条是精髓：如果「最好情况」都赢不了「已知的最好」，那就没必要试了。

5. 限界剪枝：把「最好情况」算得更准

回溯的剪枝靠「上界估计」。估计得越准，砍得越多。

限界剪枝（分支限界）换了个搜索方式：不深度优先，而是按「希望大小」排队，先搜最有可能的。

估价函数通常写成：

f(i) = g(i) + h(i)

• g(i)：从起点到当前节点，已经付出的代价
• h(i)：从当前节点到目标，估计还要付多少

这就是 A* 算法。 教材里明说：限界剪枝实质上就是 A* 算法。

关键在 h 必须「乐观」——它不能高估，否则可能把一个真正的最优解砍掉。

这是启发式算法的通病：估计函数一旦不「乐观」，你就可能错过正确答案，而且永远不知道。

四、把五张表摆在一起，能得到什么

结论一：复杂度不是唯一的评价标准。

贪心 O(n log n) 最快，但错。蛮力 Ω(2ⁿ) 最慢，但对。中间三个才是能用的。

真做工程的时候，判断顺序应该是：

1. 先问对不对（能否证明正确性，或者有没有反例）
2. 再问复杂度能不能接受（数据规模多大）
3. 最后才问能不能更快

顺序反了，就会写出又快又错的代码。 而且这种 bug 极难发现——它大部分时候是对的。

结论二：所有「聪明的算法」都在做同一件事——避免重复。

• 动态规划：记住算过的子问题
• 回溯剪枝：跳过不可能更好的分支
• 限界剪枝：排序，先走希望大的
• 分治：合并两个小问题的结果

没有一个是「算得更快」，全是「算得更少」。

这是我认为整个算法设计里最重要的一句话：

算法优化的本质不是让每一步更快，是让总步数更少。

结论三：选择比技巧重要。

同一个问题，选错范式的代价是指数级的。选对了，剩下的只是实现细节。

所以我一直认为，「算法设计」真正的难点不在写，在判断该用哪个。

五、怎么判断该用哪个：四个问题

这是我自己的决策顺序，不是教材里的。但比背五个模板有用：

问题一：能不能直接算出来？

如果能，就用最直接的。别为了优雅而上算法。 n=100 的时候，冒泡排序就是最好的选择。

问题二：能不能切成同样的小问题？

能，而且子问题独立 → 分治。

问题三：能不能从局部推全局？

能证明「贪心选择一定在最优解里」→ 贪心。不能 → 别用，再快也错。

问题四：有没有重复的子问题？

有，而且状态能用不大的数表示 → 动态规划。 没有，但解空间可以用树表示 → 回溯 / 限界。

四个问题问完，方法基本就定了。剩下的都是细节。

六、这一组文章的收尾

四篇下来，我想说的其实是同一件事：

计算机能解决的问题，比你想的少；但解决的方法，比你想的多。

• 有些问题做不了（可计算性）——分清「我不会」和「它不存在」
• 有些问题做不动（复杂度）——知道天花板在哪，不做无用功
• 剩下的问题，换一种看法就换一个难度（算法设计）

这三句话，就是「计算机学科整体观」的实际用处。

它不会让你多会一门语言，但它能让你在动手之前就知道：这件事值不值得做，以及该往哪个方向使劲。

参考与出处

本文涉及的页码均逐页核对过（教材为《算法设计与分析（微课版）》，扫描件与文本版页码差 13）：

文中所有代码片段、复杂度对照表、四个决策问题、以及那个「贪心输给最优」的具体例子，都是我自己写的，不是原书内容。 引文只做短句摘引，用于标明出处。

顺带说一句：我核这几处页码时，按目录推了一遍，五处全偏了一页（目录给的是小节起始页，正文会顺延）。所以我在这组文章里没有一个页码是推出来的，全部是逐页翻的。引用这件事，猜一次就可能错一次。