问题的形式描述 目标函数 ∑px 1≤i<n 约束条件 Mx1≤M 0≤x≤1,D.>0,w,>0.1≤i≤n 可行解:满足上述约束条件的任(x1,x2,,xn)都是问题 的一个可行解——可行解可能为多个。 (X1,x2,…,x)称为问题的一个解向量 最优解:能够使目标函数取最大值的可行解是问题的最优解 —最优解也可能为多个
问题的形式描述 目标函数： 约束条件： 可 行 解：满足上述约束条件的任一(x1 ,x2 ,…,xn ) 都是问题 的一个可行解——可行解可能为多个。 (x1 ,x2 ,…,xn )称为问题的一个解向量 最 优 解：能够使目标函数取最大值的可行解是问题的最优解 ——最优解也可能为多个。 in 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）以容量作为度量标准 以目标函数作为度量标准所存在的问题：尽管背包的效 益值每次得到了最大的增加，但背包容量也过快地被消耗掉 了，从而不能装入“更多”的物品。 改进：让背包容量尽可能慢地消耗，从而可以尽量装入 “较多”的物品。 即，新的标准是：以容量作为度量 该度量标准下的处理规则： ● 按物品重量的非降次序将物品装入到背包； ● 如果正在考虑的物品放不进去，则只取其一部分装 满背包；