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

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

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

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

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

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

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

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

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

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