贪心算法学习总结.doc

荿贪心算法袄一、算法思想肃贪心法的基本思路:艿——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。该算法存在问题:;;。膈实现该算法的过程:从问题的某一初始解出发;while能朝给定总目标前进一步do 求出可行解的一个解元素;由所有解元素组合成问题的一个可行解;羄蒄二、例题分析羀1、[背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。袇要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。羄物品袄A  莈B  罿C肄D肁E肀F蚈G膄重量wi蒂35   袂30蒇60芃50袃40芀10芆25莃价值 pi芄10羂40艿30蒃50莁35蒀40肈30薃分析:螂目标函数:∑pi最大膂约束条件是装入的物品总重量不超过背包容量:∑wi<=M(M=150)螇(1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?袇(2)每次挑选所占重量最小的物品装入是否能得到最优解?膃(3)每次选取单位重量价值最大的物品,成为解本题的策略。?虿值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。袀贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。羇可惜的是,它需要证明后才能真正运用到题目的算法中。薃一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。莁对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:薈(1)贪心策略:选取价值最大者。反例:肇W=30羄物品:A  B  C重量:281212价值:302020根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。蝿(2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。莇(3)贪心策略:选取单位重量价值最大的物品。反例:膇W=30物品:A  B  C重量:282010价值:282010根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。肁所以需要说明的是,贪心算法可以与随机化算法一起使用,具体的例子就不再多举了。(因为这一类算法普及性不高,而且技术含量是非常高的,需要通过一些反例确定随机的对象是什么,随机程度如何,但也是不能保证完全正确,只能是极大的几率正确)蒁三、贪心算法的基本要素膆1、贪心选择性质:所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。(与动态规划的主要区别)膇采用自顶向下,以迭代的方式作出相继的贪心选择,每作一次谈心选择就将所求问题简化为一个规模更小的子问题。蒂对于一个具体问题,要确定它是否具有贪心选择的性质,我们必须证明每一步所作的贪心选择最终导致问题的最优解。通常可以首先证明问题的一个整体最优解,是从贪心选择开始的,而且作了贪心选择后,原问题简化为一个规模更小的类似子问题。然后,用数学归纳法证明,通过每一步作贪心选择,最终可得到问题的一个整体最优解。罿2、最优子结构性质:包含子问题的最优解腿1、设有n个活动的安排,其中每个活动都要求使用同一资源,如演讲会场,而在同一时间只允许一个活动使用这一资源。每个活动都有使用的起始时间和结束时间。问:如何安排可以使这间会场的使用率最高。芆袃活动蚁起始时间羈结束时间莆1莄1腿4螇2蒆3蒁5袁3蒆0薆6袂4芈5蕿7蚆5节3蕿8螆6芅5膂9羇7薅6莅10薃8虿8蚈11莅9蚀8蒁12莇10蒄2肁13衿11膆12薄14蒂算法:一开始选择活动1,然后依次检查活动i是否与当前已选择的所有活动相容,若相容则活动加入到已选择的活动集合中,否则不选择活动i,而继续检查下一活动的相容性。即:活动i的开始时间不早于最近加入的活动j的结束时间。薁Prodedureplan;Beginn:=length[e];a{1};j:=1;fori:=2tondoifs[i]>=f[j]thenbeginaa∪{i};j:=i;endend;羅例1[找零钱]一个小孩买了价值少于1美元的糖,并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数,每次加入一个硬币。选择硬币时所采用的贪婪准则如下:每一次选择应使零钱数尽量增大。为保证解法的可行性(即:所给的零钱等于要找的零钱数),所选择的硬币不应使零钱总数超过最终所需的数目。蚄假设需要找给小孩67美分,首先入选的是两枚25美分的硬币,第三枚入选的不能是25美分的硬币,否则硬币的选择将不可行(零钱总数超过67美分),第