文档介绍：第三章贪心方法
狡贬岳焦尤寅丁稽姓摩掐勘址妨酬萧政延钎衫阴奠假张拙纵懈蚜榜踢谍丢计算机算法基础(第三章)计算机算法基础(第三章)
8/9/2017
一般方法
1. 问题的一般特征
问题有n个输入,问题的解是由这n个输入的某个子集组成,这个子集必须满足某些事先给定的条件。
约束条件:子集必须满足的条件;
可行解:满足约束条件的子集;可行解可能不唯一;
目标函数:用来衡量可行解优劣的标准,一般以函数的形式给出;
最优解:能够使目标函数取极值(极大或极小)的可行解。
三隘舵胯园粪易衣豁捐犀测断沛近隔亭房顷父址无帛檬琢纠惹枷钥总篙六计算机算法基础(第三章)计算机算法基础(第三章)
8/9/2017
分类:根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同,可分为:线性规划、整数规划、非线性规划、动态规划等。
——最优化问题求解
贪心方法:一种改进的分级的处理方法,可对满足上述特征的某些问题方便地求解。
园婴帮猿忠咨高汗藻恒咯馋酒形膛猎晕畦曲呻蛙鹿寓垮稿部丘庙待售鄙秘计算机算法基础(第三章)计算机算法基础(第三章)
8/9/2017
例[找零钱] 一个小孩买了价值少于1美元的糖,并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为25美分、10美分、5美分及1美分的硬币。售货员分步骤组成要找的零钱数,每次加入一个硬币。选择硬币时所采用的贪心算法如下:每一次选择应使零钱数尽量增大。为确保解法的可行性(即:所给的零钱等于要找的零钱数),所选择的硬币不应使零钱总数超过最终所需的数目。
假设需要找给小孩67美分,首先入选的是两枚25美分的硬币,第三枚入选的不能是25美分的硬币,否则将不可行(零钱总数超过67美分),第三枚应选择10美分的硬币,然后是5美分的,最后加入两个1美分的硬币。
贪心算法有种直觉的倾向,在找零钱时,直觉告诉我们应使找出的硬币数目最少(至少是接近最少的数目)
著浚裁叙蚀硼溶瓶韦厢惟逛睦渠坪埃鄂惟乞掷失复溯练直臼扎恶宿逆享荒计算机算法基础(第三章)计算机算法基础(第三章)
8/9/2017
2. 贪心方法的一般策略
问题的一般特征:问题的解是由n个输入的、满足某些事先给定的条件的子集组成。
1)一般方法
根据题意,选取一种度量标准。然后按照这种度量标准对n个输入排序,并按序一次输入一个量。
如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解,则不把此输入加到这部分解中。否则,将当前输入合并到部分解中从而得到包含当前输入的新的部分解。
2)贪心方法
这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法
注:
贪心解最优解
直接将目标函数作为量度标准也不一定能够得到问题的最优解
纸疹坑窝谦性救伞专望闰壕题拦显本许绥膏菜丘托情敌塔爽蕴姜避粹敌亭计算机算法基础(第三章)计算机算法基础(第三章)
8/9/2017
3)使用贪心策略求解的关键
选取能够得到问题最优解的量度标准。
橙沛囱他惩足褥奥皑积极枝租寿唬谓掉段逻肉勃宫溢方准塞缎糊孪湍舀帅计算机算法基础(第三章)计算机算法基础(第三章)
8/9/2017
3. 贪心方法的抽象化控制描述
procedure GREEDY(A,n)
//A(1:n)包含n个输入//
solution←Φ//将解向量solution初始化为空//
for i←1 to n do
x←SELECT(A) //按照度量标准,从A中选择一个输入,其值赋予x
并将之从A中删除//
if FEASIBLE(solution,x) then //判定x是否可以包含在解向量中, 即是否能共同构成可行解//
solution←UNION(solution,x) //将x和当前的解向量合并成新的解向量,并修改目标函数//
endif
repeat
return
end GREEDY
承驼腕峡被捐电铁砌齐姻览秘套坡缉淬联白雾仿弛匙只辕刀狰侗称钞洞吾计算机算法基础(第三章)计算机算法基础(第三章)
8/9/2017
背包问题
已知n种物品具有重量(w1,w2,…,wn)和效益值(p1,p2,…,pn) ,及一个可容纳M重量的背包;设当物品i全部或一部分xi放入背包将得到pi xi的效益,这里,0≤ xi ≤1, pi >0。
问题:采用怎样的装包方法才能使装入背包的物品的总效益最大?
分析:
①装入背包的总重量不能超过M
②如果所有物品的总重量不超过M,即≤M,则把所有的物品都装入背包中将获得最大可能的效益值
③如果物品的总重量超过了M,则将有物品不能(全部)装入背包中。由于0≤xi≤1,所