贪心算法秘籍

从前，有一个很穷的人救了一条蛇的命，蛇为了报答他的救命之恩，于是就让这个人提出要求，满足他的愿望。这个人一开始只要求简单的衣食，蛇都满足了他的愿望，后来慢慢的贪欲生起，要求做官，蛇也满足了他。这个人直到做了宰相还不满足，还要求做皇帝。蛇此时终于明白了，人的贪心是永无止境的，于是一口就把这个人吞掉了。

所以，蛇吞掉的是宰相，而不是大象。故此，留下了“人心不足蛇吞相”的典故。后来也逐渐演变为“贪心不足蛇吞象”。

2.1　人之初，性本贪

我们小时候背诵《三字经》，“人之初，性本善，性相近，习相远。”其实我觉得很多时候“人之初，性本贪”。小孩子吃糖果，总是想要多多的；吃水果，想要最大的；买玩具，总是想要最好的，这些东西并不是大人教的，而是与生俱来的。对美好事物的趋优性，就像植物的趋光性，“良禽择木而栖，贤臣择主而事”“窈窕淑女，君子好逑”，我们似乎永远在追求美而优的东西。现实中的很多事情，正是因为趋优性使我们的生活一步一步走向美好。例如，我们竭尽所能买了一套房子，然后就想要添置一些新的家具，再就想着可能还需要一辆车子……

凡事都有两面性，一把刀可以做出美味佳肴，也可以变成杀人凶器。在这里，我们只谈好的“贪心”。

2.1.1　贪心本质

一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。

——《算法导论》

我们经常会听到这些话：“人要活在当下”“看清楚眼前”……贪心算法正是“活在当下，看清楚眼前”的办法，从问题的初始解开始，一步一歩地做出当前最好的选择，逐步逼近问题的目标，尽可能地得到最优解，即使达不到最优解，也可以得到最优解的近似解。

贪心算法在解决问题的策略上“目光短浅”，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法能得到许多问题的整体最优解或整体最优解的近似解。因此，贪心算法在实际中得到大量的应用。

在贪心算法中，我们需要注意以下几个问题。

（1）没有后悔药。一旦做出选择，不可以反悔。

（2）有可能得到的不是最优解，而是最优解的近似解。

（3）选择什么样的贪心策略，直接决定算法的好坏。

那么，贪心算法需要遵循什么样的原则呢？

2.1.2　贪亦有道

“君子爱财，取之有道”，我们在贪心算法中“贪亦有道”。通常我们在遇到具体问题时，往往分不清哪些问题该用贪心策略求解，哪些问题不能使用贪心策略。经过实践我们发现，利用贪心算法求解的问题往往具有两个重要的特性：贪心选择性质和最优子结构性质。如果满足这两个性质就可以使用贪心算法了。

（1）贪心选择

所谓贪心选择性质是指原问题的整体最优解可以通过一系列局部最优的选择得到。应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后续的贪心策略状态空间图中得到深刻的体会。

（2）最优子结构

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题是否可用贪心算法求解的关键。例如原问题S={a1，a2，…，ai，…，an}，通过贪心选择选出一个当前最优解{ai}之后，转化为求解子问题S−{ai}，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质，如图2-1所示。

图2-1　原问题和子问题

2.1.3　贪心算法秘籍

武林中有武功秘籍，算法中也有贪心秘籍。上面我们已经知道了具有贪心选择和最优子结构性质就可以使用贪心算法，那么如何使用呢？下面介绍贪心算法秘籍。

（1）贪心策略

首先要确定贪心策略，选择当前看上去最好的一个方案。例如，挑选苹果，如果你认为个大的是最好的，那你每次都从苹果堆中拿一个最大的，作为局部最优解，贪心策略就是选择当前最大的苹果；如果你认为最红的苹果是最好的，那你每次都从苹果堆中拿一个最红的，贪心策略就是选择当前最红的苹果。因此根据求解目标不同，贪心策略也会不同。

（2）局部最优解

根据贪心策略，一步一步地得到局部最优解。例如，第一次选一个最大的苹果放起来，记为a1，第二次再从剩下的苹果堆中选择一个最大的苹果放起来，记为a2，以此类推。

（3）全局最优解

把所有的局部最优解合成为原来问题的一个最优解（a1，a2，…）。

怎么有点儿像冒泡排序啊？

“不是六郎似荷花，而是荷花似六郎”！不是贪心算法像冒泡排序，而是冒泡排序使用了贪心算法，它的贪心策略就是每一次从剩下的序列中选一个最大的数，把这些选出来的数放在一起，就得到了从大到小的排序结果，如图2-2所示。

本文来自本人著作《趣学算法》。