第4章贪心方法ppt课件.ppt

《第4章贪心方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章贪心方法8/7/2021本章教学要求及重点难点理解贪心方法的基本思想掌握背包问题的求解方法掌握带有限期的作业排序的基本方法掌握用贪心方法求解单源点最短路径的基本方法。重点：用贪心方法求背包问题及带有限期作业排序；难点：用贪心方法求单源点最短路径。8/7/20214.1一般方法1.问题的一般特征问题有n个输入，问题的解是由这n个输入的某个子集组成，这个子集必须满足某些事先给定的条件。约束条件：子集必须满足的条件；可行解：满足约束条件的子集；可行解可能不唯一；目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出；最优解：能够使目标函数取极值（极大或极小）的可行解。分类：根据描

2、述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。——最优化问题求解贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些问题方便地求解。8/7/2021例[找零钱]一个小孩买了价值少于1元的糖，并将1元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为25分、10分、5分及1分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的

3、数目。假设需要找给小孩67分，首先入选的是两枚25分的硬币，第三枚入选的不能是25分的硬币，否则将不可行（零钱总数超过67分），第三枚应选择10分的硬币，然后是5分的，最后加入两个1分的硬币。贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）8/7/20212.贪心方法的一般策略问题的一般特征：问题的解是由n个输入的、满足某些事先给定的条件的子集组成。1）一般方法根据题意，选取一种度量标准。然后按照这种度量标准对n个输入排序，并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入

4、加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的新的部分解。2）贪心方法这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法注：贪心解最优解直接将目标函数作为量度标准也不一定能够得到问题的最优解3）使用贪心策略求解的关键选取能够得到问题最优解的量度标准。8/7/20213.贪心方法的抽象化控制描述procedureGREEDY(A,n)//A(1:n)包含n个输入//solution←Φ//将解向量solution初始化为空//fori←1tondox←SELECT(A)//按照度量标准，从A中选择一个输入，其值赋予x并将之从A中删除//ifFEASIB

5、LE(solution,x)then//判定x是否可以包含在解向量中，即是否能共同构成可行解//solution←UNION(solution,x)//将x和当前的解向量合并成新的解向量，并修改目标函数//endifrepeatreturn(solution)endGREEDY8/7/20214.2背包问题1.问题的描述已知n种物品具有重量(w1,w2,…,wn)和效益值(p1,p2,…,pn)，及一个可容纳M重量的背包；设当物品i全部或一部分xi放入背包将得到pixi的效益，这里，0≤xi≤1,pi>0。问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？分析：①装入背包的

6、总重量不能超过M②如果所有物品的总重量不超过M，即≤M，则把所有的物品都装入背包中将获得最大可能的效益值③如果物品的总重量超过了M，则将有物品不能（全部）装入背包中。由于0≤xi≤1，所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为M的若干物品（整个或一部分）目标：使装入背包的物品的总效益达到最大。8/7/2021问题的形式描述目标函数：约束条件：可行解：满足上述约束条件的任一集合(x1,x2,…,xn)都是问题的一个可行解——可行解可能为多个。(x1,x2,…,xn)称为问题的一个解向量最优解：能够使目标函数取最大值的可行解是问题的最优解——最优解也可能为多个。8/

7、7/2021例4.1背包问题的实例设，n=3，M=20，(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)。可能的可行解如下：(x1,x2,x3)①(1/2,1/3,1/4)16.524.25//没有放满背包//②(1,2/15,0)2028.2③(0,2/3,1)2031④(0,1,1/2)2031.58/7/20212.贪心策略求解度量标准的选择：三种不同的选择1）以目标函数作为度量标准即，每装入一件物品，就使背包背包获得最大可