5.2 贪心算法的分析

这一节将重点讨论适用贪心方法可以求解的问题所具有的一般性质。对于一个具体的问题，怎么知道是否可以用贪心算法解此问题，以及能否得到问题的最优解呢？这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有两个重要性质：贪心选择和最优子结构性质。

1.贪心选择性质

所谓贪心选择性质，是指所求问题的整体最优解可以通过一系列局部最优的选择，即通过贪心选择来实现。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

前面的章节中介绍了动态规划思想通常以自底向上的方式解各个子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式逐个做出贪心选择，每做一次贪心选择，所求问题将简化为规模更小的子问题。对于一个具体的问题而言，要确定该问题是否具有贪心选择性质，必须证明每一步所做的贪心选择将最终产生问题的整体最优解，然而证明过程通常需要一些技巧来完成。通常来说，可以在证明过程中先考察一个全局最优解，然后证明可以通过修改这个最优解，使其采用贪心选择，这个选择会使原问题变为一个相似的、规模更小的问题。

2.最优子结构性质

当一个问题的最优解包含其子问题的最优解时，则称该问题具有最优子结构性质。最优子结构性质是一个问题是否可以用动态规划或贪心算法求解的关键特征。基于对最优子结构的观察，能够写出描述一个最优解值的递归式，从而写出解决问题的算法。但是需要注意的是，并非所有具有最优子结构性质的问题都可以采用贪心策略来得到最优解，这一点将在后面章节中所介绍的背包问题中看到。

虽然贪心算法和动态规划算法都要求问题具有最优子结构性质，但是二者却存在着巨大的差别，具体差别见表5-1。

表5-1 贪心算法和动态规划算法性质比较

3.贪心算法的基本步骤