贪心算法：只顾眼前最优，未必得到全局最好的结果

在计算机算法的世界里，贪心算法是一种思路简单、上手很快的策略。它的核心逻辑很直白：每一步都只做当下看起来最好的选择，不往长远预判，不回头推翻之前的决定，一路沿着局部最优走下去。但它有一个很关键的局限 ——每一步的最优，叠加起来，不一定是整件事的最优解。

很多生活场景都能类比贪心算法。比如凑零钱，假设面额是 1 元、5 元、10 元，要凑 14 元。贪心思路会优先选面额最大的：先拿 10 元，再拿两个 1 元，一共 3 张纸币，这就是最优方案。在这个场景下，贪心是奏效的。

可如果换一套特殊面额：1 元、7 元、10 元，目标凑 14 元。按照贪心策略，先选最大的 10 元，剩下 4 元只能用四张 1 元，总共 5 张。但真正最优方案其实是两张 7 元，只需要 2 张。这里就能清晰看见贪心的短板：它只盯着眼前最大的选择，看不到几步之后的全局组合，掉进了局部最优的陷阱。

放到计算机程序里也是同理。贪心算法在每一次决策节点，只评估当前这一刻收益最高的选项，不会枚举所有可能性，也不会回溯修改已经做出的决定。正因为不用大量计算未来分支，它运行速度快、代码简洁，资源消耗很低，适合数据量大、对运算速度要求高的场景。像哈夫曼编码、最小生成树、活动时间安排，这些场景的特性刚好满足贪心的条件，局部最优可以通向全局最优，贪心算法就成了首选。

但贪心有严格的适用前提，并不是所有问题都适配。它要求问题具备两个特质：一是贪心选择性质，也就是局部最优能够推导出全局最优；二是最优子结构，一个问题的最优解包含子问题的最优解。一旦缺少这两个条件，贪心就容易给出次优甚至很差的结果。经典的背包问题就是典型例子：背包有固定承重，物品有重量和价值，想装出总价值最高的组合。如果贪心只一味选单位价值最高的物品，很容易提前占满背包，漏掉价值更高的组合。

这也是算法工程师需要权衡的地方。贪心算法胜在简单高效，代价是视野短浅；想要保证拿到全局最优，往往就要使用动态规划、暴力搜索等方案，但它们会消耗更多算力、时间。

贪心算法更像一种做事哲学：只顾当下的最优选择，是省力的捷径，却未必能抵达最好的终点。算法没有绝对的好坏，只有适不适合场景。懂得分辨什么时候可以放心 “贪心”，什么时候必须着眼全局、长远规划，才是算法设计里重要的功课。