贪心算法2 #

1. 贪心算法存在的问题
2. 贪心算法的基本要素
3. 贪心算法的证明(仅做了解)

贪心算法存在的问题 #

贪心算法不能保证解所求解问题是最佳的。因为贪心算法总是从局部出发，并没从整体考虑。

例如给出一个正整数n，寻找最少的完全平方数，使他们的和为n：
我们仍使用上节课例子的贪心解法，把比这个数小的最大的完全平方数加进这个数中，比如对于12来说，最大的完全平方数是9，剩下的事情是凑3，那么比3小的最大的完全平方数就是1，最终使用贪心的算法求解出12=9+1+1+1，一共使用了4个完全平方数，可是，12可以使用3个4来表示。可见此时使用贪心算法并未得到最优解。

贪心算法的基本要素 #

贪心选择的性质:所求解问题的最优解，可以通过一系列局部最优解的选择，即贪心选择来达到。贪心选择的性质是贪心算法可行的第一要素

最优子结构：当一个问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。最优子结构是贪心算法的关键特征

贪心选择的性质，实际就是贪心算法的可行性进行证明，我们不做要求。
最优子结构的理解我们仍以上节课找零钱为例：对于25 分、10 分、5 分和 1 分四种硬币,如果给客户41分的零钱，易得到[25,10,5,1]是该问题的最优解。那么由每步产生的最优解组成的任意子问题，都是子问题的最优解。例如[10,5,1]是16分零钱的最优解，[10,1]是11分零钱的最优解。

贪心算法的证明 #

贪心算法可行性的证明是贪心算法的最难点，并不要求掌握，一般步骤如下(本质上是数学归纳法)：

1.首先证明存在一个最优解，该最优解是以贪心策略选择开始

2.证明所求解问题具有最优子结构

反之如果证明贪心算法不可行，我们仅需举出一个反例即可。仍以上述找硬币的例子为例，但是此时只有14分,10分,6分,1分四种硬币，如果要给客户找16分零钱，仍以上述贪心算法做选择，那么可得16=14+1+1,需要3枚硬币。而16=10+6仅需两枚硬币，即可证明贪心算法不具备可行性。

小结 #

理解最优子结构含义

掌握贪心算法的基本要素

习题 #

1. 理解最优子结构含义，并举出具有最优子结构的问题
2. 尽可能多举出能使用贪心算法解决的问题