5.设计一个递归算法实现贪心策略。 6.将递归算法转换为迭代算法。
在这个过程中，我们详细地看到了贪心算法是如何以动态规划方法为基础的。例如，在活动选择问题中，我们首先定义了子问题Sij，其中2和7都是可变的。然后我们发现，如果总是做出贪心选择，则可以将子问题限定为Sk的形式。
与这种繁琐的过程相反，我们可以通过贪心选择来改进最优子结构，使得选择后只留下一个子问题。在活动选择问题中，我们可以一开始就将第二个下标去掉，将子问题定义为Sk的形式。然后，我们可以证明，贪心选择(Sk中最早结束的活动am)与剩余兼容活动集的最优解组合在一起，就会得到Sk的最优解。更一般地，我们可以按如下步骤设计贪心算法:
1.将最优化问题转化为这样的形式:对其做出一次选择后，只剩下一个子问题需要求解。
2.证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。 3.证明做出贪心选择后，剩余的子问题满足性质:其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
在本章剩余部分中，我们将使用这种更直接的设计方法。但我们应该知道，在每个贪心算法之下，几乎总有一个更繁琐的动态规划算法。
我们如何证明一个贪心算法是否能求解一个最优化问题呢?并没有适合所有情况的方法，但贪心选择性质和最优子结构是两个关键要素。如果我们能够证明问题具有这些性质，就向贪心算法迈出了重要一步。
贪心选择性质
第一个关键要素是贪心选择性质(greedy choice property):我们可以通过做出局部最优(贪心)选择来构造全局最优解。换句话说，当进行选择时，我们直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。
这也是贪心算法与动态规划的不同之处。在动态规划方法中，每个步骤都要进行一次选择，但选择通常依赖于子问题的解。因此，我们通常以一种自底向上的方式求解动态规划问题，先求解较小的子问题，然后是较大的子问题(我们也可以自顶向下求解，但需要备忘机制。当然，即使算法是自顶向下进行计算，我们仍然需要先求解子问题再进行选择)。在贪心算法中，我们总是做出当时看来最佳的选择，然后求解剩下的唯一的子问题。贪心算法进行选择时可能依赖之前做出的选择，但不依赖任何将来的选择或是子问题的解。因此，与动态规划先求解子问题才能进行第一次选择不同，贪心算法在进行第一次选择之前不求解任何子问题。一个动态规划算法是自底向上进行计算的，而一个贪心算法通常是自顶向下的，进行一次又一次选择，将给定问题实例变得更小。
当然，我们必须证明每个步骤做出贪心选择能生成全局最优解。如定理16. 1所示，这种证明通常首先考查某个子问题的最优解，然后用贪心选择替换某个其他选择来修改此解，从而得到一个相似但更小的子问题。
如果进行贪心选择时我们不得不考虑众多选择，通常意味着可以改进贪心选择，使其更为高效。例如，在活动选择问题中，假定我们已经将活动按结束时间单调递增顺序排好序，则对每个活动能够只需处理一次。通过对输人进行预处理
或者使用适合的数据结构(通常是优先队列)，我们通常可以使贪心选择更快速，从而得到更高效的算法。
最优子结构
如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。此性质是能否应用动态规划和贪心方法的关键要素。我们还是以16.1节的活动选择问题为例，如果一个子问题Sij的最优解包含活动ak，那么它必然也包含子问题Sik和Skj的最优解。给定这样的最优子结构，我们可以得出结论，如果知道Sij的最优解应该包含哪个活动ak，就可以组合ak以及Sik和Skj的最优解中所有活动来构造Sij的最优解。基于对最优子结构的这种观察结果，我们就可以设计出递归式(16.2)来描述最优解值的计算方法。
当应用于贪心算法时，我们通常使用更为直接的最优子结构。如前所述，我们可以假定，通过对原问题应用贪心选择即可得到子问题。我们真正要做的全部工作就是论证:将子问题的最优解与贪心选择组合在一起就能生成原问题的最优解。这种方法隐含地对子问题使用了数学归纳法，证明了在每个步骤进行贪心选择会生成原问题的最优解。
贪心对动态规划
由于贪心和动态规划策略都利用了最优子结构性质，你可能会对一个可用贪心算法求解的问题设计一个动态规划算法，或者相反，对一个实际上需要用动态规划求解的问题使用了贪心方法。为了说明两种方法之间的细微差别，我们研究一个经典最优化问题的两个变形。
0-1背包问题(0-1 knapsack problem)是这样的:一个正在抢劫商店的小偷发现了n个商品，第i个商品价值vi美元，重wi磅，vi和wi都是整数。这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳W磅重的商品，W是一个整数。他应该拿哪些商品呢?(我们称这个问题是0-1背包问题，因为对每个商品，小偷要么把它完整拿走，要么把它留下;他不能只拿走一个商品的一部分，或者把一个商品拿走多次。)
在分数背包问题(fractional knapsack problem)中，设定与0-1背包问题是一样的，但对每个商品，小偷可以拿走其一部分，而不是只能做出二元((0-1)选择。你可以将0-1背包问题中的商品想象为金锭，而分数背包问题中的商品更像金砂。
两个背包问题都具有最优子结构性质。对0-1背包问题，考虑重量不超过W而价值最高的装包方案。如果我们将商品j从此方案中删除，则剩余商品必须是重量不超过W-wj的价值最高的方案(小偷只能从不包括商品j的n-1个商品中选择拿走哪些)。
虽然两个问题相似，但我们用贪心策略可以求解分数背包问题，而不能求解0-1背包问题。为了求解分数背包问题，我们首先计算每个商品的每磅价值vi /wi。遵循贪心策略，小偷首先尽量多地拿走每磅价值最高的商品。如果该商品已全部拿走而背包尚未满，他继续尽量多地拿走每磅价值第二高的商品，依此类推，直至达到重量上限W。因此，通过将商品按每磅价值排序，贪心算法的运行时间为O(n lgn)。
为了说明这一贪心策略对0-1背包问题无效，考虑图16-2(a)所示的问题实例。此例包含3个商品和一个能容纳50磅重量的背包。商品1重10磅，价值60美元。商品2重20磅，价值100美元。商品3重30磅，价值120美元。因
此，商品1的每磅价值为6美元，高于商品2的每磅价值(<5美元)和商品3的每磅价值(<4美元)。因此，上述贪心策略会首先拿走商品1。但是，如图16-2(b)的实例分析所示，最优解应该拿走商品2和商品3，而留下商品1。拿走商品1的两种方案都是次优的。
但是，如图16-2(c)所示，对于分数背包问题，上述贪心策略首先拿走商品1，是可以生成最优解的。拿走商品1的策略对0-1背包问题无效是因为小偷无法装满背包，空闲空间降低了方案的有效每磅价值。在0-1背包问题中，当我们考虑是否将一个商品装入背包时，必须比较包含此商品的子问题的解与不包含它的子问题的解，然后才能做出选择。这会导致大量的重叠子问题—动态规划的标识。