华中科技大学：《计算机算法基础》 第三章 贪心方法

第三章贪心方法

第三章 贪心方法

3.1一般方法 1.问题的一般特征 问题有n个输入,问题的解是由这n个输入的某个子集组成,这个子 集必须满足某些事先给定的条件 约束条件:子集必须满足的条件; 可行解:满足约束条件的子集;可行解可能不唯一; 目标函数:用来衡量可行解优劣的标准,一般以函数的形式给出 最优解:能够使目标函数取极值(极大或极小)的可行解。 分类:根据描述问题约束条件和目标函数的数学模型的特性和问题的 求解方法的不同,可分为:线性规划、整数规划、非线性规划、动态规 划等 —最优化问题求解 贪心方法:一种改进的分级的处理方法,可对满足上述特征的某些问 题方便地求解

3.1 一般方法 1. 问题的一般特征 问题有n个输入，问题的解是由这n个输入的某个子集组成，这个子 集必须满足某些事先给定的条件。 ◼ 约束条件：子集必须满足的条件； ◼ 可 行 解：满足约束条件的子集；可行解可能不唯一； ◼ 目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出； ◼ 最 优 解：能够使目标函数取极值（极大或极小）的可行解。 分类：根据描述问题约束条件和目标函数的数学模型的特性和问题的 求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规 划等。 ——最优化问题求解 贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些问 题方便地求解

2.贪心方法的一般策略 问题的一般特征:问题的解是由n个输入的、满足某些事先给定的 条件的子集组成。 1)一般方法 根据题意,选取一种度量标准。然后按照这种度量标准对η个输入 排序,并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在 起不能产生一个可行解,则不把此输入加到这部分解中。否则,将当前 输入合并到部分解中从而得到包含当前输入的新的部分解 这一处理过程一直持续到n个输入都被考虑完毕,则记入最优解集 合中的输入子集构成这种量度意义下的问题的最优解 贪心方法:这种能够得到某种量度意义下的最优解的分级处理方法 称为贪心方法 注 贪心解亠最优解 直接将目标函数作为量度标准也不一定能够得到问题的最优解 使用贪心策略求解的关键是选取能够得到问题最优解的量度标准

2. 贪心方法的一般策略 问题的一般特征：问题的解是由n个输入的、满足某些事先给定的 条件的子集组成。 1）一般方法 根据题意，选取一种度量标准。然后按照这种度量标准对n个输入 排序，并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一 起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前 输入合并到部分解中从而得到包含当前输入的新的部分解。 这一处理过程一直持续到n个输入都被考虑完毕，则记入最优解集 合中的输入子集构成这种量度意义下的问题的最优解 贪心方法: 这种能够得到某种量度意义下的最优解的分级处理方法 称为贪心方法 注： ➢ 贪心解 最优解 ➢ 直接将目标函数作为量度标准也不一定能够得到问题的最优解 ➢ 使用贪心策略求解的关键是选取能够得到问题最优解的量度标准。 ？ ＝

3.贪心方法的抽象化控制描述 procedure GREEDY(A, n) ∥A(1:n)包含n个输入∥ solution←Φ∥将解向量 solution初始化为空∥ fori←1 ton do ⅹ← SELECT(A)∥/按照度量标准,从A中选择一个输入, 其值赋予x并将之从A中删除∥ if feas|BLE( olution,x)then∥.定x是否可以包含在当前解向量 中,即是否能共同构成可行解/∥/ solution←UN|ON( solution,x)∥.x和当前的解向量合并成 新的解向量,并修改目标函数 endif repeat return end GREeDY

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

3.2背包问题 1问题的描述 已知n种物品具有重量w1,W2,…,Wwn)和效益值(D1,p2…,pn),及一个 可容纳M重量的背包;设当物品全部或一部分x放入背包将得到pX的效 益,这里,0≤X≤1,p1>0。 问题:采用怎样的装包方法才能使装入背包的物品的总效益最大? 分析: ①装入背包的总重量不能超过M ②如果所有物品的总重量不超过M,即∑mx≤M,则把所有的物 品都装入背包中将获得最大可能的效益值 ③如果物品的总重量超过了M,则将有物品不能(部分/全部)装 入背包中。由于0≤xi≤1,所以可以把物品的一部分装入背包,故最终 背包中可刚好装入重量为M的若干物品(整体或一部分)。这种情况下, 如果背包没有被装满,则显然不能获得最大的效益值。 目标:使装入背包的物品的总效益达到最大

3.2 背包问题 1.问题的描述 已知n种物品具有重量(w1 ,w2 ,…,wn )和效益值(p1 ,p2 ,…,pn ) ，及一个 可容纳M重量的背包；设当物品i全部或一部分xi放入背包将得到pi xi的效 益，这里，0≤ xi ≤1, pi >0。 问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？ 分析： ① 装入背包的总重量不能超过M ② 如果所有物品的总重量不超过M，即 ≤M，则把所有的物 品都装入背包中将获得最大可能的效益值 ③ 如果物品的总重量超过了M，则将有物品不能（部分/全部）装 入背包中。由于0≤xi≤1，所以可以把物品的一部分装入背包，故最终 背包中可刚好装入重量为M的若干物品（整体或一部分）。这种情况下， 如果背包没有被装满，则显然不能获得最大的效益值。 目标：使装入背包的物品的总效益达到最大。  in i i w x 1

问题的形式描述 目标函数 ∑px 1≤i0,w,>0.1≤i≤n 可行解:满足上述约束条件的任(x1,x2,,xn)都是问题 的一个可行解——可行解可能为多个。 (X1,x2,…,x)称为问题的一个解向量 最优解:能够使目标函数取最大值的可行解是问题的最优解 —最优解也可能为多个

问题的形式描述 目标函数： 约束条件： 可 行 解：满足上述约束条件的任一(x1 ,x2 ,…,xn ) 都是问题 的一个可行解——可行解可能为多个。 (x1 ,x2 ,…,xn )称为问题的一个解向量 最 优 解：能够使目标函数取最大值的可行解是问题的最优解 ——最优解也可能为多个。  in i i p x 1 x p w i n w x M i i i i n i i           0 1, 0, 0,1 1

例3.1背包问题的实例 设,n=3,M=20, (p1p2,p3)=(25,24,15),(W1,W2,W3)=(18,15,10)。 可能的可行解如下 )∑x∑ ①(1/2,1/3,14)16.52425m没有装满背包∥ ②2(1,2/15,0)20 28.2 ③(0,2/3,1)20 ④(0,1,12)20 31.5

例3.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.5  i i  p x i i w x

2.贪心策略求解 度量标准的选择:三种不同的选择 1)以目标函数作为度量 即,每装入一件物品,就使背包获得最大可能的效益增量 该度量标准下的处理规则是: 按效益值的非增次序将物品一件件地放入到背包: ●如果正在考虑的物品放不进去,则只取其一部分装满背包:如 果该物品的一部分不满足获得最大效益增量的度量标准,则在剩下的物 品种选择可以获得最大效益增量的其它物品,将它或其一部分装入背包。 如:若△M=2,背包外还剩两件物品i,j,且有(p=4,W1=4)和(p 3,w=2),则下一步应选捅而非放入背包 p/2=2p=3

2. 贪心策略求解 度量标准的选择：三种不同的选择 1）以目标函数作为度量 即，每装入一件物品，就使背包获得最大可能的效益增量。 该度量标准下的处理规则是： ● 按效益值的非增次序将物品一件件地放入到背包； ● 如果正在考虑的物品放不进去，则只取其一部分装满背包：如 果该物品的一部分不满足获得最大效益增量的度量标准，则在剩下的物 品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。 如：若ΔM=2,背包外还剩两件物品i,j，且有(pi＝ 4，wi＝4) 和(pj ＝ 3，wj＝2)，则下一步应选择j而非i放入背包： pi /2 = 2 ＜ pj＝ 3

实例分析(例31) p1→p2>p 首先将物品1放入背包,此时x1=1,背包获得p1=25的效益增量,同时 背包容量减少W1=18个单位,剩余空间△M=2 其次考虑物品2和3。就ΔM=2而言有,只能选择物品2或3的一部分装入 背包 物品2:若ⅹ2=2/15,则p2X2=16/5=3.1 物品3:若X3=2/10,则p3x3=3 为使背包的效益有最大的增量,应选择物品2的2/15装包,即 x2=2/15 最后,背包装满,△M=0,物品3不装包,即x3=0 背包最终可以获得效益值=X1p1+x2p2+x3p3 282(次优解,非问题的最优解)

实例分析（例3.1) ∵ p1＞p2＞ p3 ∴ 首先将物品1放入背包，此时x1＝1，背包获得p1＝25的效益增量，同时 背包容量减少w1＝18个单位，剩余空间ΔM=2。 其次考虑物品2和3。就ΔM=2而言有，只能选择物品2或3的一部分装入 背包。 物品2： 若 x2＝2/15， 则 p2 x2＝16/5＝3.1 物品3： 若 x3＝2/10， 则 p3 x3＝3 为使背包的效益有最大的增量，应选择物品2的2/15装包，即 x2＝2/15 最后，背包装满，ΔM=0，物品3不装包，即x3＝0 。 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 28.2 (次优解,非问题的最优解)

2)以容量作为度量标准 以目标函数作为度量标准所存在的问题:尽管背包的效 益值每次得到了最大的增加,但背包容量也过快地被消耗掉 ,从而不能装入“更多”的物品。 改进:让背包容量尽可能慢地消耗,从而可以尽量装入 较多”的物品。 即,新的标准是:以容量作为度量 该度量标准下的处理规则: ●按物品重量的非降次序将物品装入到背包; ●如果正在考虑的物品放不进去,则只取其一部分装 满背包;

2）以容量作为度量标准 以目标函数作为度量标准所存在的问题：尽管背包的效 益值每次得到了最大的增加，但背包容量也过快地被消耗掉 了，从而不能装入“更多”的物品。 改进：让背包容量尽可能慢地消耗，从而可以尽量装入 “较多”的物品。 即，新的标准是：以容量作为度量 该度量标准下的处理规则： ● 按物品重量的非降次序将物品装入到背包； ● 如果正在考虑的物品放不进去，则只取其一部分装 满背包；