贪心算法2 #
- 贪心算法存在的问题
- 贪心算法的基本要素
- 贪心算法的证明(仅做了解)
贪心算法存在的问题 #
例如给出一个正整数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分零钱的最优解。
贪心算法的证明 #
贪心算法可行性的证明是贪心算法的最难点,并不要求掌握,一般步骤如下(本质上是数学归纳法):
反之如果证明贪心算法不可行,我们仅需举出一个反例即可。仍以上述找硬币的例子为例,但是此时只有14分,10分,6分,1分四种硬币,如果要给客户找16分零钱,仍以上述贪心算法做选择,那么可得16=14+1+1,需要3枚硬币。而16=10+6仅需两枚硬币,即可证明贪心算法不具备可行性。
小结 #
习题 #
- 理解最优子结构含义,并举出具有最优子结构的问题
- 尽可能多举出能使用贪心算法解决的问题