文档介绍：贪心算法论文姓名:高翔班级:706指导老师:范江文一概念;贪心,贪心顾名思义即不顾一切地追求目标。在FreePascal中贪心算法可以解释为:从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续。前进时,算法停止。这时就得到了问题的一个解,但不能保证求得的最后解是最优的。在改进算法中,贪心算法演化为爬山法。注意:贪心算法并不能保证求得的解是最优的,一定要三思而后行!!二特点及使用范围贪心算法的优点在于时间复杂度极低。而贪心算法与其他最优化算法的区别在于:它具有不可后撤性,可以有后效性,一般情况下不满足最优化原理。贪心算法的特点就决定了它的适用范围,它一般不适用于解决可行性问题,仅适用于较容易得到可行解的最优性问题。这里较容易得到可行解的概念是:当前的策略选择后,不会或极少使后面出现无解的情况。另外,对于近年来出现的交互性题目,贪心算法是一个较好的选择。这是因为,在题目中,一个策略的结果是随题目的进行而逐渐给出的,我们无法预先知道所选策略的结果,这与贪心算法不考虑策略的结果和其具有后效性的特点是不谋而合的。当然,贪心算法还可以为搜索算法提供较优的初始界值。三经典例题 例一背包问题有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。   要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。   物品ABCDEFG   重量35306050401025   价值10403050354030   分析:   目标函数:∑pi最大   约束条件是装入的物品总重量不超过背包容量:∑wi<=M(M=150)   (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?   (2)每次挑选所占重量最小的物品装入是否能得到最优解?   (3)每次选取单位重量价值最大的物品,成为解本题的策略。   值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。   贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。   可惜的是,它需要证明后才能真正运用到题目的算法中。   一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。   对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:   (1)贪心策略:选取价值最大者。反例:   W=30   物品:ABC   重量:281212   价值:302020   根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。   (2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。   (3)贪心策略:选取单位重量价值最大的物品。反例:   W=30   物品:ABC   重量:282010   价值:282010根据策略,三种物品单位重量价值一样,程序无法依据现有策略做出判断,如果选择A,则答案错误。注意:此题用贪心算法解的确不错,但不是最优解。解此题思路⒈建立数学模型来描述问题。⒉把求解的问题分成若干个子问题。⒊对每一子问题求解,得到子问题的局