贪心算法的基本内容

贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时看起来是最佳的选择。这种启发式策略并不是总能产生最优解，但正如我们在哈夫曼问题中看到的那样，它常常能给出最优解。此篇文章我们来讨论讨论贪心算法的某些一般性质。

一般的，我们可以根据如下的步骤来设计贪心算法：

• 先优化问题转换成这样一个话题，即先做出选择，在决定剩下的一个子问题
• 证明原问题总是有一个最优解是由贪心选择得到的，从而说明贪心选择的安全
• 说明在做出贪心选择后，剩余的子问题有这样一个性质。即如果将子问题的最优解和我们所做的贪心选择联合起来，可以得出原问题的一个最优解

无论如何，在每一个贪心算法的下面，几乎总是会有一个更加复杂的动态规划解

贪心算法是否能够解决一个特定的最优化问题呢？一般来说不是，但是贪心选择性质和最优子结构是两个关键的特点。如果我们能证明问题具有这些性质，那么就可以设计出他的一个贪心算法。

贪心选择性质

第一个关键特点是贪心选择性质：一个全局最优解可以通过局部最优（贪心）选择来达到。换句话说，当考虑做何选择时，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。

这一点是贪心算法不同于动态规划之处。在动态规划中，每一步都要做出选择，但是这些选择依赖于子问题的解。因此，解动态规划问题一般是自底向上，从小子问题处理至大字问题。贪心算法所做的当前选择可能依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解。因此，不像动态规划方法那样自底向上解决子问题，贪心算法通常是自顶向下的做的，一个一个地做出贪心选择，不断地将给定的问题实例归纳为更小的问题。

当然我们必须证明在每一步所做的贪心选择最终能产生一个全局最优解这也正是需要技巧的所在。一般来说，现在证明中考察一个全局最优解，然后证明可对该解进行修改，使其使用贪心选择，这个选择将原问题变为一个相似的、但更小的问题

贪心选择性质时面对子问题做出选择时，通常能帮助我们提高效率。通常对数据进行处理或选用合适的数据结构（优先队列），能够使贪心选择更加迅速，因而产生出一个高效的算法。

最优子结构

对于一个问题来说，如果它的一个最优解包含了其子问题的最优解，则称该问题有最优子结构。

这个性质是用来对动态规划以及贪心算法的可应用性进行评价的关键一点。

在贪心算法中使用最优子结构时，通常使用更直接的方式。假设在原问题中做了一个贪心选择而得到一个子问题，真正要做的是证明此子问题的最优解与所做的贪心选择合并后，的确可以得到原问题的一个最优解。这个方案意味着要对子问题采用归纳法，来证明每个步骤中所做的贪心选择最终会产生出一个最优解。