有一种算法它做每个决定时都只看眼前最好的选项从不回头从不懊悔。它有个恰如其分的名字——贪心算法。它有时天才有时会犯下让人捧腹的错误。一、先认识这位及时行乐者想象你是一只松鼠正在森林里觅食准备过冬。每到一棵树前你都只看这棵树上的松果最多还是最少——选最多的那棵摘了就走不管前方的树有没有更好的。这就是贪心算法的精髓在每一步选择中总是做出当前看来最优的决策且不会回头修改。它的英文名 greedy algorithmgreedy原意就是贪婪、只顾眼前。核心思想把一个大问题拆成一系列子问题在每个子问题上都取局部最优解最后把这些局部最优拼成全局答案——然后祈祷结果是正确的。贪心算法在很多问题上表现出色Dijkstra最短路径算法、Huffman压缩编码、Prim和Kruskal最小生成树……都是贪心策略的经典胜利。它们简洁、高效是计算机科学的优美篇章。但是……它也会翻车。而且翻车的方式往往让人醍醐灌顶。二、第一个陷阱找零钱找零钱是贪心算法的经典教材案例。假设你要找给顾客11分钱贪心策略很直观每次都选面值最大的硬币直到凑够为止。当硬币面值是 1分、5分、10分 时这个策略完美奏效10111只需2枚。但如果换一套面值呢找零钱互动演示标准面值 [1, 5, 10]特殊面值 [1, 5, 7]目标金额11分。贪心策略每次选最大面值的硬币。贪心结果每次选最大面值1¢1¢1¢1¢7¢共 5 枚 ✓ 成功最优解动态规划5¢5¢1¢共 3 枚 ✓ 最优贪心多用了 2 枚硬币 原因选了 7¢ 后剩 4分无法用 5¢ 了。看到了吗面值换成 1、5、7 后贪心策略选了 7然后只剩 4分只能用 4枚1分凑齐——共5枚。但最优解是 5513枚少用了2枚有便宜就占绝不回头——贪心算法的格言有时是智慧有时是陷阱。问题的根源在于贪心选了一个当下最大的硬币但这个选择堵死了后续更优的组合路径。它缺乏预见性。三、第二个陷阱0/1 背包问题想象你是个冒险家背包限重10公斤面前有4件宝物。贪心策略建议按性价比价值/重量从高到低拿。听起来聪明对不对背包问题对比贪心策略按性价比最优策略动态规划 钻石3kg · ¥40性价比 13.3已选 珠宝4kg · ¥50性价比 12.5已选 金块7kg · ¥70性价比 10.0 古画6kg · ¥55性价比 9.2重量上限10kg已用重量7kg / 10kg贪心结果¥90 钻石 珠宝最优结果¥110 金块 钻石⚠ 贪心少收获了 ¥20 选性价比最高不等于总价值最高——因为物品不能切割重量组合受限制。这就是著名的0/1背包问题——每件物品要么拿要么不拿不能切割。贪心在这里彻底失效因为物品之间存在组合关联选了A就没位置放B和C但BC的价值可能远超A。而如果物品可以任意切割分数背包贪心则恰好给出最优解——微小的条件差异导致算法的命运天差地别。四、局部最优的山峰全局最优的山谷贪心算法最形象的困境可以用一座山来说明。想象你在山地里目标是爬到最高峰但你的策略是永远朝当前看得见的最陡方向走。局部最优 vs 全局最优局部最优h 130全局最优h 170贪心者到顶了真正的顶峰需先下山(贪心不允许)起点贪心者爬上左峰后因不肯先下降再上升永远错过了右边更高的山这就是贪心算法最本质的局限它只能找到局部最优解无法保证全局最优。在机器学习中梯度下降也面临同样困境——鞍点和局部极小值是深度学习训练的老大难问题。五、贪心算法合法上岗的条件贪心并非总是错的它在某些问题上确实能给出全局最优解。但这需要问题满足两个苛刻条件⚡贪心选择性质全局最优解可以通过一系列局部最优选择来到达——当前的贪心选择不会破坏后续子问题的最优性。最优子结构问题的最优解包含其子问题的最优解——大问题的最优能由小问题的最优拼出来。数学家用拟阵理论Matroid Theory来严格界定哪些问题可以用贪心求解。拟阵是一种抽象的数学结构凡是满足拟阵特性的问题贪心算法必定能给出最优解。Kruskal算法之所以正确正是因为图的生成树结构恰好构成一个拟阵。有趣的是标准硬币系统1分、5分、1角、5角、1元之所以刚好适合贪心找零并非偶然——面值的倍数关系在数学上保证了贪心选择性质。换一套不规则面值这个性质立刻消失。六、旅行商与集合覆盖贪心的滑铁卢旅行商问题TSP一位推销员要遍访 n 个城市各一次再回出发点如何走总路程最短贪心策略说每次去最近的未访问城市。听起来合理实则可能比最优路线长出 20%30%而且城市越多偏差越难以预测。TSP 是 NP 难问题——目前没有任何已知算法能在合理时间内保证对任意规模的输入找到最优解。全球每年有大量算法竞赛、物流优化项目在尝试近似解决它。集合覆盖问题假设你要用最少的广播电台覆盖全国所有省份。贪心策略每次选覆盖未覆盖省份最多的电台。这个策略给出的是近似解最坏情况下比最优解多用 O(log n) 个电台——这个误差是有数学保证的也是目前人类能做到的最好近似。近似比的魅力对于这类 NP 难问题贪心算法虽然找不到精确最优解但它往往能给出还不算太差的近似解——并且速度极快。在工程实践中8成好但秒出结果往往比100%最优但算一周更有价值。七、算法的局限也是人生的镜子贪心算法的故事讲的不只是代码。每一步都选当下最好并不等于走出了最好的路。我们的大脑在很多时候也在运行贪心算法选利润最高的项目而不是成长空间最大的选最省力的社交关系而放弃了需要磨合才能深厚的友情选眼下最舒服的选项错过了要先下坡再上山的机会。然而贪心也并不总是错误。它之所以在算法世界里如此受欢迎恰恰是因为它的简洁和高效。很多时候足够好且快速远胜于完美但迟缓。贪心算法真正的智慧在于知道自己什么时候适用。Dijkstra 知道最短路径问题满足贪心选择性质所以它大胆用贪心并能给出完美答案背包问题不满足所以我们换动态规划——回溯、记录、综合权衡。人生的道理也许如此有些问题当机立断就是最好的策略有些问题你需要容忍当下的下坡才能抵达真正的高峰。能分辨这两种情形才是真正的智慧。一个有趣的问题留给你思考你今天的某个决定是在用贪心策略还是动态规划你确定这道题适合贪心吗参考资料《Hello算法》图解贪心算法一章 · Wikipedia 贪心算法 · Pearson, D. (2005) A polynomial-time algorithm for the change-making problem. · 知乎贪心算法背后的数学理论拟阵· Kruskal Prim 算法原论文。