贪心算法，好用说完了，局限呢？
有一种算法，它做每个决定时都只看眼前最好的选项，从不回头，从不懊悔。它有个恰如其分的名字——贪心算法。它有时天才，有时会犯下让人捧腹的错误。
一、先认识这位"及时行乐者"
想象你是一只松鼠，正在森林里觅食准备过冬。每到一棵树前，你都只看这棵树上的松果最多还是最少——选最多的那棵，摘了就走，不管前方的树有没有更好的。
这就是贪心算法的精髓：在每一步选择中，总是做出当前看来最优的决策，且不会回头修改。它的英文名 "greedy algorithm"，"greedy"原意就是贪婪、只顾眼前。
核心思想：把一个大问题拆成一系列子问题，在每个子问题上都取局部最优解，最后把这些局部最优拼成全局答案——然后祈祷结果是正确的。
贪心算法在很多问题上表现出色：Dijkstra最短路径算法、Huffman压缩编码、Prim和Kruskal最小生成树……都是贪心策略的经典胜利。它们简洁、高效，是计算机科学的优美篇章。
但是……它也会翻车。而且翻车的方式，往往让人醍醐灌顶。
二、第一个陷阱：找零钱
找零钱是贪心算法的经典教材案例。假设你要找给顾客11分钱，贪心策略很直观：每次都选面值最大的硬币，直到凑够为止。
当硬币面值是 1分、5分、10分 时，这个策略完美奏效：10+1=11，只需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枚。但最优解是 5+5+1=3枚，少用了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，但B+C的价值可能远超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 算法原论文。