在这个充满了逻辑与数据的数字宇宙里我们常常听到各种各样的名词，有的听起来高深莫测，有的则显得颇为接地气。今天我想和大家聊聊一个特别有意思，甚至带点“人性”色彩的算法策略——贪心算法。

说实话，第一次听到这个名字的时候，我的脑海里浮现的竟然是那个经典的手机游戏“贪吃蛇”。毕竟听起来dou是那种不知满足、一路狂吃的感觉。但随着对编程理解的加深，我才恍然大悟，原来这不仅仅是一个简单的游戏逻辑，geng是一种解决复杂问题的深刻哲学。它就像是一个在人生十字路口，总是只盯着眼前利益Zui大化的决策者，虽然听起来有点短视，但在特定的规则下它却Neng带我们走向终点。

Ru果我们要给贪心算法下个定义，其实并不复杂。在对问题进行求解的过程中，它总是Zuo出在当前kan来是Zui好的选择。也就是说它不从整体Zui优上加以考虑，它所Zuo出的仅是在某种意义上的局部Zui优解。

这听起来是不是有点像我们生活中的某些时刻？比如减肥时面对一块蛋糕，当下的Zui优解显然是“吃掉它”，因为那Neng带来瞬间的快乐。当然人生这种复杂问题不Neng只kan眼前，但在算法的世界里Ru果这种“当下的快乐”Neng够一步步推导出“Zui终的幸福”，那贪心策略就是无敌的。

这种策略的核心逻辑在于：每一步dou选择当前状态下Zui好的选项，寄希望于通过一系列的局部Zui优选择，Neng够Zui终导向全局的Zui优解。这就像是一场没有彩排的即兴演出，演员不需要知道剧本的结局，只需要演好当下的每一幕。

为了不让这个概念显得太抽象，我们不妨把目光投向一个日常生活中极其常见的场景——零钱兑换。

想象一下你去超市购物，买了一堆零食，总价是23元。你递给收银员一张100元的大钞，现在问题来了：收银员该怎样给你找零，才Neng既让你满意，又让收银台的硬币数量Zui少呢？

这是一个非常经典的优化问题。对于人类来说这简直是不假思索的本Neng。你会根据还剩余的找零额度，从可选择的币种中选择面值Zui大的。先拿一张50元，剩27元；再拿一张20元，剩7元；接着一张5元，剩2元；Zui后两枚1元。搞定。

整个过程行云流水，会100以内加减法的人douNeng轻易搞定。这背后其实就是贪心算法在起作用：在每一步找零时dou优先选择面值Zui大的硬币。

我们来kankan这段逻辑Ru果用代码来表达，会是怎样的景象。这里有一段JavaScript的实现，虽然简单，却道尽了贪心的精髓：

/* 零钱兑换：贪心策略实现 */
function calculateChange {
    // 
得把面额排个序，从小到大或者从大到小douKe以
    // 这里假设传入的 denominations Yi经是有序的，比如 
    let resultCount = 0;
    let currentAmount = targetAmount;
    // 指针指向Zui大面额的索引
    let i = denominations.length - 1;
    // 只要还有余额没找完，我们就一直循环
    while  {
        // Ru果当前Zui大的硬币比剩余金额大，那就换个小点的面额
        while  {
            i--;
        }
        // 找到了合适的硬币，那就选它！
        currentAmount -= denominations;
        resultCount++;
    }
    // Ru果Zui后余额归零，皆大欢喜，返回硬币数；否则返回-1表示无解
    return currentAmount === 0 ? resultCount : -1;
}

你kan，代码的逻辑和我们大脑的思考过程几乎是一模一样的。这种算法的优点显而易见：操作直接、实现简单，通常效率也hen高。毕竟它不需要像动态规划那样去回溯计算所有的可Neng性，它只顾着一路向前冲。

这里必须得泼一盆冷水。贪心算法虽然好用，但它并不是万Neng钥匙。它Neng够找到Zui优解的前提是局部Zui优确实Neng导致全局Zui优。Ru果这个前提不成立，贪心策略就会像一个迷路的孩子，把你带进沟里。

还是找零问题。Ru果我们国家的硬币面额不是现在的这样，而是比较奇葩的组合，比如：面额有 三种硬币。现在要找零 6 元。

按照贪心的逻辑，我们先选Zui大的 4 元，剩 2 元；然后只Neng选两个 1 元。总共用了 3 枚硬币。

但是稍微动动脑子就知道，Zui优解明明是两枚 3 元的硬币，只需要 2 枚！

kan吧，这就是贪心的局限性。在币值种类不够“完美”的情况下它那种“只kan眼前”的短视行为，直接导致了结果的非Zui优。所以在使用贪心算法之前，我们必须得像数学家一样严谨地证明：这个问题到底适不适合贪心？

除了找零，贪心算法还有一个著名的战场——背包问题。不过这里有个大坑，得先说清楚。

我们今天讨论的是“分数背包问题”，而不是那个大名鼎鼎的“0-1背包问题”。这俩的区别可大了去了。

想象一下你是一个强盗，闯进了一个宝库。你有一个背包，容量是有限的。宝库里有hen多金银财宝，每件物品dou有它的重量和价值。

Ru果是“0-1背包”，那你面对每件物品只NengZuo两个选择：要么完整地拿走，要么一点dou不拿。不Neng把金项链砍断带走一半。这种情况下贪心算法往往会失效，因为你为了拿一个价值密度高但体积大的东西，可Neng会浪费掉hen多空间，导致总价值不如拿几个小件物品划算。

但是Ru果是“分数背包”，情况就完全不同了。规则允许你选择物品的一部分，价值根据你选择的重量比例计算。比如一袋金粉太重了你Ke以只倒一半进背包，拿走一半的价值。

这时候，贪心算法就又行了！

策略非常简单：计算所有物品的“性价比”。然后毫不犹豫地先拿性价比Zui高的，拿完再拿次高的……直到背包塞满为止。

这个问题的解答策略和“找零”类似：Zui大化背包内物品总价值，本质上是Zui大化单位重量下的物品价值。局部Zui优必然导向全局Zui优。

kan到这里你可Neng会问：“我到底什么时候该用贪心，什么时候又得老老实实用动态规划呢？”

这确实是个问题。贪心算法没有固定的算法框架，它不像二分查找或者快速排序那样有标准的模板。算法设计的关键是贪心策略的选择。

一般来说Ru果一个问题想用贪心解决，通常需要关注两个性质：

1. 贪心选择性质这是指一个全局Zui优解Ke以通过一系列局部Zui优的选择来达到。这意味着我们不需要回溯，不需要后悔，每一步选定了就定局了。 2. 无后效性这是个hen专业的词。意思就是某个状态以后的过程不会影响以前的状态，只与当前状态有关。一旦Zuo出了某个选择，未来的决策就只依赖于当前剩下的资源，而与之前是如何达到这个状态的无关。这就像翻篇了过去的事就过去了只kan当下。

除了上面介绍的找零和分数背包，贪心的适用场景还包括但不限于：霍夫曼编码、Zui小生成树、活动选择问题等等。

在这些领域，贪心策略往往Neng展现出惊人的效率。相比于动态规划那种“杀鸡用牛刀”的繁琐，贪心算法就像是一把锋利的手术刀，精准且快速。

写到这里我不禁感叹，算法真的是人类思维的一种投射。贪心算法，这个听起来有些“自私”的名字，其实蕴含着一种极致的实用主义。

我们往往无法预知未来无法掌握所有的信息。我们就像那个在迷宫里探索的人，不知道出口在哪里。这时候，与其站在原地计算所有可Neng的路径，不如选一条眼前kan起来Zui顺的路先走着。

虽然这种方法不Neng保证我们每次douNeng找到Zui短的路径，甚至可Neng走进死胡同，但它至少让我们动了起来让我们在有限的时间里获得了前进的可Neng。

正如上海交通大学硕士、华为高级算法工程师靳宇栋在《Hello，算法》中所提到的那样，算法不仅仅是代码，geng是解决问题的思维方式。贪心算法教会我们，在资源有限、信息不全的情况下如何Zuo出Zui利于当下的决策。

当然我们也要时刻警惕，不要让“贪心”变成了“盲目”。在代码里我们Ke以通过数学证明来验证贪心的正确性；但在人生中，每一次“局部Zui优”的选择，dou可Neng需要我们付出巨大的机会成本。

所以算法世界里的贪心，是一种智慧；而现实世界里的贪心，则需要geng多的智慧去驾驭。希望这篇文字，Neng让你在下次敲下 `while` 循环或者 `sort` 函数时Neng多一份对“当下”与“未来”的思考。

geng多好文第一时间接收，可关注公众号：“前端说书匠”。我们下期见！