一个贪心算法是通过做一系列的选择来给出某一问题的最优解的。对算法中的每一决策点，做一个当时（看似）最佳的选择。这种启发式策略并不是总能产生出最优解。但正象我们在引例中那样，它常常给出最优解。这里我们介绍贪心方法的某些的一般性质。

对一个最优化问题，什么情况能用贪心算法？没有一个通用的方法。但适宜于贪心策略来解的问题大多都有两个特点：贪心的选择性质和最优子结构。

• 贪心选择性质

所谓贪心的选择性质是指：一个全局最优解可通过做局部最优（贪心）选择来达到。这一点是贪心算法与动态规划的不同之处。动态规划在每一步也要做选择，但所做的选择可能要依赖于子问题的解。在一个贪心算法中，我们所做的总是当前（看似）最佳的选择，然后再解决做了该选择之后所出现的子问题。贪心算法所做的当前选择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解。贪心算法通常是自顶向下地解出问题，一个一个做出贪心选择，不断地将给定的问题实例归约为更小规模的问题。由于贪心算法的每一步选择都仅做一次，无重复回溯过程，所以它具有很高的时间效率。

对于一个具体的问题，要确定它是否具有贪心选择性，我们必须证明在每一步所做的贪心选择最终能产生一个全局的最优解，而这是需要技巧的。典型地，我们在证明中先考察一个全局最优解，然后再证明可对该解加以修改，使其第一步为一个贪心选择，这个选择将原问题变为一个相似的、但又更小的问题。这样，我们就可用归纳法证明其每一步所做的都是贪心选择，证明了做一次贪心选择就可把问题归约为相似但规模更小的问题，实际上也就把对正确性的证明转化为说明一个最优解必须具有最优子结构的问题。当然，对有的问题，也可以象引例中的证明那样，先假设有一个最优解，证明最优解的每一步一定是贪心选择。

• 最优子结构

所谓最优子结构是指：问题的最优解包含了子问题的最优解。这个性质是用来对某问题判断是否可用动态规划算法或贪心算法的关键点。例如引例中当进行一次贪心的选择后，问题转化为一个规模小的子问题，对于某一个最优解，其中子问题必定是最优的。

• 贪心法与动态规划算法

贪心法与动态规划法都利用了最优子结构的性质，故我们往往会在贪心解足以解决的情况下用动态规划法求解，或者相反，在必须用动态规划法求解场合下用贪心法。这两种技术之间的区别是很细微的。只要我们在平时积累大量的经验，在解题时，对这两种算法的选择才能做到应用自如。下面我们考察换硬币问题的两种变形问题。

例1　找换硬币

    试用最少的硬币来找n分钱。

      A.假设可换的硬币的单位有c^0,c^1,…，c^k。整数c>1，k≥1。

      B.可换的硬币的单位是任意的正整数。

以上两种变形的换硬币问题都具有最优子结构。对于情况A，可以看成是情况B的一种特例。对于情况A，可以贪心策略来解决问题，而对于情况B，却不行。

对于情况A的找换硬币问题，找n分钱，我们总是选出一枚面值不超过n的最大的硬币ci，然后将n减去 ci，对剩下的钱，再按一枚面值不超过它的的最大硬币，如此进行下去，直到剩下的钱为0为止。下面证明这种贪心法的正确性。

事实上，对于任一找换方案，除了最大面值的硬币外，某一种硬币c^i的个数最多不会超过c-1，因为若这种硬币c^i的个数多于c-1个，则至少可以用一个c^(i+1)硬币代替c个c^i硬币，从而使得新的方案更优。下面我们证明，找n分钱，对于面值不超过n的最大的硬币c^k我们必选一个。显然n≥c^k，若最优方案中不选择硬币c^k，则只能选择c^0，c^1，…，c^(k-1)这些硬币，而且每且硬币最多只能有c-1枚（上面已证）。但（c-1）*(c^0+c^1+…+c^(k-1))= c^(k-1)< c^k≤n。所以若不选硬币c^k，则无法找n分钱。

以上我们证明了问题的贪心选择性。因此对于情况A的找换硬币问题可以用贪心法求解。而对于情况B的找换硬币问题显然是不一定符合最优选择性的，我们很容易得到它的反例。如硬币的面值为一分、五分和一角一分三种，而要找1角五分。如果按贪心法则要找一枚一角一分硬币和三枚的一分硬币，共4枚硬币。而最优解是三枚5分硬币。在最优方案中，必须对所有选择了某一枚硬币的子问题进行比较，看哪个子问题找换的硬币比较少。这种方式形成的子问题导致了许多重迭性的子问题，这是动态规划方法的一个特征。我们可以用动态规划法求解情况B的找换硬币问题。

评：以上所说的“贪心”算法是正统的“贪心”算法，可以出最优解的那种。在某些较优化问题中，可以用“贪心”法求较优解，实际上也是构造算法中的一种。这一类题目在IOI'97中有具体的例子。同时也是竞赛捞分的重要手段之一。