03-贪心本质

2.1.1　贪心本质

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

——《算法导论》

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

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

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

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

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

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

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