第4章贪心方法名师编辑PPT课件.ppt
2023-11-3第四章第四章 贪心方法贪心方法2023-11-3本章教学要求及重点难点本章教学要求及重点难点n理解贪心方法的基本思想理解贪心方法的基本思想n掌握背包问题的求解方法掌握背包问题的求解方法n掌握带有限期的作业排序的基本方法掌握带有限期的作业排序的基本方法n掌握用贪心方法求解单源点最短路径的基本方掌握用贪心方法求解单源点最短路径的基本方法。法。n重点：用贪心方法求背包问题及带有限期作业重点：用贪心方法求背包问题及带有限期作业排序；排序；n难点：用贪心方法求单源点最短路径。难点：用贪心方法求单源点最短路径。2023-11-34.1 一般方法一般方法1.问题的一般特征问题的一般特征 问题有问题有n个输入，问题的解是由这个输入，问题的解是由这n个输入的某个个输入的某个子集子集组成，这个子组成，这个子集必须满足某些事先给定的条件。集必须满足某些事先给定的条件。n 约束条件约束条件：子集必须满足的条件；：子集必须满足的条件；n 可行解可行解：满足约束条件的子集；可行解可能不唯一；：满足约束条件的子集；可行解可能不唯一；n 目标函数目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出；：用来衡量可行解优劣的标准，一般以函数的形式给出；n 最优解最优解：能够使目标函数取极值（极大或极小）的可行解。：能够使目标函数取极值（极大或极小）的可行解。分类分类：根据描述问题约束条件和目标函数的：根据描述问题约束条件和目标函数的数学模型数学模型的特性和问题的的特性和问题的求解方法求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。划等。最优化问题求解最优化问题求解 贪心方法贪心方法：一种改进的：一种改进的分级分级的处理方法，可对满足上述特征的某些问的处理方法，可对满足上述特征的某些问题方便地求解。题方便地求解。2023-11-3例例找零钱找零钱 一个小孩买了价值少于一个小孩买了价值少于1元的糖，并将元的糖，并将1元的钱元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为设提供数目不限的面值为25分、分、10分、分、5分及分及1分的硬币。分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心算法如下：每一次选择应使零钱选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。所需的数目。假设需要找给小孩假设需要找给小孩67分，首先入选的是两枚分，首先入选的是两枚25分的硬币，分的硬币，第三枚入选的不能是第三枚入选的不能是25分的硬币，否则将不可行（零钱总分的硬币，否则将不可行（零钱总数超过数超过67分），第三枚应选择分），第三枚应选择10分的硬币，然后是分的硬币，然后是5分的，分的，最后加入两个最后加入两个1分的硬币。分的硬币。贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）应使找出的硬币数目最少（至少是接近最少的数目）2023-11-32.贪心方法的一般策略贪心方法的一般策略 问题的一般特征：问题的解是由问题的一般特征：问题的解是由n个输入的、满足某些事先给定个输入的、满足某些事先给定的条件的子集组成。的条件的子集组成。1）一般方法）一般方法 根据题意，选取一种根据题意，选取一种度量标准度量标准。然后按照这种度量标准对。然后按照这种度量标准对n个输个输入入排序排序，并按序一次输入一个量。，并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的如果这个输入和当前已构成在这种量度意义下的部分最优解部分最优解加在加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的当前输入合并到部分解中从而得到包含当前输入的新的部分解新的部分解。2）贪心方法）贪心方法 这种能够得到某种量度意义下的最优解的这种能够得到某种量度意义下的最优解的分级处理分级处理方法称为方法称为贪心贪心方法方法注：注：贪心解贪心解 最优解最优解 直接将目标函数作为直接将目标函数作为量度标准量度标准也不一定能够得到问题的最优解也不一定能够得到问题的最优解 3）使用贪心策略求解的关键）使用贪心策略求解的关键 选取能够得到问题最优解的量度标准。选取能够得到问题最优解的量度标准。？2023-11-33.贪心方法的抽象化控制描述贪心方法的抽象化控制描述 procedure GREEDY(A,n)/A(1:n)包含包含n个输入个输入/solution /将解向量将解向量solution初始化为空初始化为空/for i1 to n do xSELECT(A)/按照度量标准，从按照度量标准，从A中选择一个输入，其值赋予中选择一个输入，其值赋予x 并将之从并将之从A中删除中删除/if FEASIBLE(solution,x)then /判定判定x是否可以包含在解向量中，是否可以包含在解向量中，即是否能共同构成可行解即是否能共同构成可行解/solutionUNION(solution,x)/将将x和当前的解向量合并成新的解和当前的解向量合并成新的解 向量，并修改目标函数向量，并修改目标函数/endif repeat return(solution)end GREEDY 2023-11-34.2 背包问题背包问题1.问题的描述问题的描述 已知已知n种物品具有重量种物品具有重量(w1,w2,wn)和效益值和效益值(p1,p2,pn)，及一个，及一个可容纳可容纳M重量的背包；设当物品重量的背包；设当物品i全部或一部分全部或一部分xi放入背包将得到放入背包将得到pi xi的的效益，这里，效益，这里，0 xi 1,p 1,pi 0 0。问题问题：采用怎样的装包方法才能使装入背包的物品的：采用怎样的装包方法才能使装入背包的物品的总效益最大总效益最大？分析分析：装入背包的总重量装入背包的总重量不能超过不能超过M M 如果所有物品的如果所有物品的总重量总重量不超过不超过M M，即，即 MM，则把，则把所有所有的物的物品都装入背包中将获得最大可能的效益值品都装入背包中将获得最大可能的效益值 如果物品的总重量如果物品的总重量超过了超过了M M，则将有物品不能（全部）装，则将有物品不能（全部）装 入背包中。由于入背包中。由于0 xi1xi1，所以可以把物品的一部分装入背包，所以最，所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为终背包中可刚好装入重量为M M的若干物品（整个或一部分）的若干物品（整个或一部分）目标目标：使装入背包的物品的：使装入背包的物品的总效益总效益达到达到最大最大。niiixw12023-11-3问题的形式描述问题的形式描述 目标函数目标函数：约束条件约束条件：可可 行行 解解：满足上述约束条件的：满足上述约束条件的任一集合任一集合(x1,x2,xn)都是问题都是问题 的一个可行解的一个可行解可行解可能为多个。可行解可能为多个。(x1,x2,xn)称为问题的一个称为问题的一个解向量解向量 最最 优优 解解：能够使目标函数取：能够使目标函数取最大值最大值的可行解是问题的的可行解是问题的 最优解最优解最优解也可能为多个。最优解也可能为多个。niiixp1niwpxMxwiiiniii1,0,0,1012023-11-3例例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.5 24.25 /没有放满背包没有放满背包/(1,2/15,0)20 28.2 (0,2/3,1)20 31 (0,1,1/2)20 31.5iixpiixw2023-11-32.贪心策略求解贪心策略求解 度量标准的选择：三种不同的选择度量标准的选择：三种不同的选择1）以）以目标函数目标函数作为度量标准作为度量标准 即，每装入一件物品，就使背包背包获得即，每装入一件物品，就使背包背包获得最大最大可能的效益增可能的效益增量。量。该度量标准下的该度量标准下的 处理规则：处理规则：按效益值的非增次序将物品一件件地放入到背包；按效益值的非增次序将物品一件件地放入到背包；如果正在考虑的物品放不进去，则只取其一部分装满背包：如如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在果该物品的一部分不满足获得最大效益增量的度量标准，则在剩下剩下的物的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。如：若如：若M=2M=2,背包外还剩两件物品背包外还剩两件物品i,ji,j，且有，且有(pi 4，wi4)和和(pj 3，wj2)，则下一步应选择，则下一步应选择j而非而非i放入背包：放入背包：pi/2=2 pj 32023-11-3实例分析（例实例分析（例4.1)(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)p1p2 p3 首先将首先将物品物品1 1放入背包，此时放入背包，此时x11，背包获得，背包获得p125的效益增量，同时背包容的效益增量，同时背包容量减少量减少w118个单位，剩余空间个单位，剩余空间M=2M=2。其次考虑其次考虑物品物品2 2和和3 3。就。就M=2M=2而言有，只能选择物品而言有，只能选择物品2 2或或3 3的的一部分一部分装入背包。装入背包。物品物品2 2：若若 x22/15，则则 p2 x216/53.1 物品物品3 3：若若 x32/10，则则 p3 x33 为使背包的效益有最大的增量，应选择为使背包的效益有最大的增量，应选择物品物品2的的2/15装包，即装包，即 x22/15 最后，背包装满，最后，背包装满，M=0M=0，故，故物品物品3 3将不能装入背包，将不能装入背包，x30 。背包最终可以获得背包最终可以获得效益值效益值 x1 p1 x2 p2x3 p3 28.2 (次优解次优解,非问题的最优解非问题的最优解)2023-11-32）以）以容量容量作为度量标准作为度量标准 以以目标函数目标函数作为度量标准所存在的问题：尽管背包的效作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入了，从而不能装入“更多更多”的物品。的物品。改进：让背包改进：让背包容量容量尽可能慢地消耗，从而可以尽量装入尽可能慢地消耗，从而可以尽量装入“更多更多”的物品。的物品。即，新的标准是：以即，新的标准是：以容量容量作为度量标准作为度量标准 该度量标准下的处理规则：该度量标准下的处理规则：按物品按物品重量的非降次序重量的非降次序将物品装入到背包；将物品装入到背包；如果正在考虑的物品放不进去，则只取其一部分装如果正在考虑的物品放不进去，则只取其一部分装满背包；满背包；2023-11-3实例分析（例实例分析（例4.1)(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)w3w2 w1 首先将首先将物品物品3 3放入背包，此时放入背包，此时x31，背包容量减少，背包容量减少w310个单个单位，还剩余空间位，还剩余空间M=10M=10。同时，。同时，背包获得背包获得p315的效益增量的效益增量。其次考虑其
