第七章背包问题(第9讲)

1、 第七章第七章 背包问题背包问题 Optimizing Methods第七章第七章 背包问题背包问题1 背包问题的描述背包问题的描述2 背包问题的分支定界法背包问题的分支定界法3 背包问题的近似算法背包问题的近似算法第七章第七章 背包问题背包问题 背包问题背包问题 ( Knapsack Problem ) 是一个有着广泛应是一个有着广泛应用的组合优化问题，它不仅在投资决策、装载、库存等用的组合优化问题，它不仅在投资决策、装载、库存等方面有应用，而且常以子问题形式出现在大规模优化问方面有应用，而且常以子问题形式出现在大规模优化问题中，它的理论与算法具有一定的代表性题中，它的理论与算法具有一定的代

2、表性. 背包问题的一般描述为：设有物品集背包问题的一般描述为：设有物品集是一个准备放入容量为是一个准备放入容量为 的背包中的的背包中的 n 项物品的集项物品的集合合. 12,nUu uuCZ物品物品 的重量为的重量为 价值为价值为jujwZjpZ如何选择如何选择 U 中的一些物品装入背包，使这些物品的中的一些物品装入背包，使这些物品的总重量不超过总重量不超过 C ，且使总价值达到最大？，且使总价值达到最大？1 1 背包问题的描述背包问题的描述背包问题的数学模型：背包问题的数学模型：()KP1maxnjjjzp x1. .njjjstw xC011,2,jxorjNnjwZ重量重量jpZ价值价值

3、CZ容量容量 因为决策变量因为决策变量 , ,所以也称所以也称 0-1 0-1 背包问题背包问题. .01jxor一般背包问题一般背包问题: : 01,2,jxZjNn KPNPC( General Knapsack Problem )第七章第七章 背包问题背包问题为讨论方便，总可假定（相当于标准化）：为讨论方便，总可假定（相当于标准化）：即按价值密度从大到小排列即按价值密度从大到小排列.10,01jjwpjn、；21 ;jwCjn、13njjwC、12124nnpppwww、 实际问题实际问题并非满足并非满足1 1 背包问题的描述背包问题的描述对对 4 只需只需 O(nln n)次运算即可；

4、次运算即可；对对 3 若若最优解为最优解为 ;1njjwC121nxxx对对 2 若若 ，则最优解中，则最优解中 事先可去掉事先可去掉;jwC0,jx 对对 1 分三种情况讨论分三种情况讨论:00jjpw令令00,0jjNjN pw此时，最优解中此时，最优解中 0jx 所以，该物品事先可去掉所以，该物品事先可去掉;00jjpw令令10,0jjNjN pw此时，最优解中此时，最优解中 1jx 所以，该物品事先可去掉所以，该物品事先可去掉; 容量取容量取1jCCw第七章第七章 背包问题背包问题00jjpw令令0,0jjNjN pw 只需在模型中，令只需在模型中，令 ，则系数即为大于零了，则系数即为

5、大于零了.1jjxy 综上，对不满足（综上，对不满足（1）、（）、（2）、（）、（3）的假定，可）的假定，可作如下处理，使之满足：作如下处理，使之满足：jN1jjjjjjxyppww 01()jNNNNNjjjjjjxyppww则原问题化为：则原问题化为：1maxjjjj NNj NNzp yp1. .jjjj NNj NNstw yCw01,jyorjNN1 1 背包问题的描述背包问题的描述()KP1maxnjjjzp x1. .njjjstw xC011,2,jxorjNn如果在（如果在（KP）中，令）中，令1jjxy 11maxnnjjjjjzpp y11. .nnjjjjjstww y

6、C011,2,jyorjNn令令1njjqwC1minnjjjup y1. .njjjs tw yq011,2,jyorjNn该问题的实际意义该问题的实际意义是求不放在包中的物是求不放在包中的物品的价值和最小品的价值和最小 模型的意义模型的意义Go back第七章第七章 背包问题背包问题 分支定界法分支定界法 ( Branch and Bound Method ) 的基本的基本思想在运筹学课程中已介绍，它的重要在于它提出了一思想在运筹学课程中已介绍，它的重要在于它提出了一类新的思路（隐枚举法），使得许多原来不好解决的问类新的思路（隐枚举法），使得许多原来不好解决的问题有了解决的可能性。（具有普

7、适性）题有了解决的可能性。（具有普适性）确定问题（子问题）的最优值的确定问题（子问题）的最优值的界界极大（小）化问题极大（小）化问题上（下）界上（下）界 通常是通过求解松弛问题，用松弛问题的解作为界通常是通过求解松弛问题，用松弛问题的解作为界Note 松弛问题选择的松弛问题选择的原则原则、松弛问题要与原问题的最优值尽量接近；、松弛问题要与原问题的最优值尽量接近；松弛问题要尽量容易解松弛问题要尽量容易解 . .这两个原则不易统一，所以可选择不同的松弛问题这两个原则不易统一，所以可选择不同的松弛问题2 2 背包问题的分支定界法背包问题的分支定界法划分方法的选择划分方法的选择原则是希望分出来的子问题

8、容易被查清，可加快计算原则是希望分出来的子问题容易被查清，可加快计算.选哪个活问题先检查选哪个活问题先检查先检查最大上界（极大化问题）的活问题先检查最大上界（极大化问题）的活问题优点：优点：检查子问题较其他规则为少；检查子问题较其他规则为少；缺点：缺点：计算机储存量较大计算机储存量较大先检查最新产生的最大上界的活问题先检查最新产生的最大上界的活问题优点：优点：计算机储存量较少计算机储存量较少 ；缺点：缺点：需要更多的分支运算需要更多的分支运算选择的不同，提供了发挥的余地选择的不同，提供了发挥的余地第七章第七章 背包问题背包问题考虑考虑 KP 的松弛问题的松弛问题0,10,1jjxx()C KP

9、1maxnjjjzp x1. .njjjstw xC1,2,jNn01jx0,1jx ()KPC(KP)如何求解？如何求解？思路：将物品按价值密度从大到小的顺序放入包内思路：将物品按价值密度从大到小的顺序放入包内, 记记 1minjiisjwC 关键项关键项第一个放不下的第一个放不下的物品的序号物品的序号?Theorem 2.12 2 背包问题的分支定界法背包问题的分支定界法C(KP) 最优解为最优解为111jxjs01jxjsn ssCxw其中其中11sjjCCw最优解值为最优解值为11()ssoptjjspzC KPpCwproof 显然，显然， ，()( ()optoptzKPzC KP

10、jp由于由于 的整数性，的整数性，得到得到 z ( KP ) 的一个上界：的一个上界：111( ()ssoptjjspUzC KPpCw表示不超过表示不超过 的最大整数的最大整数. .Go on Go back第七章第七章 背包问题背包问题Theorem 2.1 的证明的证明显然显然 C(KP) 的最优解必满足的最优解必满足1njjjw xC(0)jp 设设 是其最优解，是其最优解，*x要证要证*xx若存在若存在 使使ks*1kx 则至少存在则至少存在 使使 . qs*qqxx取充分小的取充分小的0(满足满足: )*1120kkqqwxxw、*,kkkqkqxwwxww则重量增加则重量减少将将

11、 增加增加 减少减少 , ,*kx*,qxkqww此时此时, ,仍是一个可行解仍是一个可行解, ,且目标函数值增加且目标函数值增加 ,()0kkqqwppw矛盾矛盾 .*,1kkksxx对同理可证同理可证*0kks x对又由极大性知：又由极大性知：*sssCxxw因此，因此， 是最优解是最优解. .x( ()optzC KP易证为最优解值Proof :2 2 背包问题的分支定界法背包问题的分支定界法Theorem 2.2设设10111ssjjspUpCw11111()ssjssjspUppwCw其中其中 与与 定义同前定义同前. .sC则则的一个上界为的一个上界为 ；1()z KP、012ma

12、x(,)UUU2、对背包问题任一实例，对背包问题任一实例， .21UU作为上界作为上界U2比比U1更更好好1w1swCsw11sjjCCwswC1111()ssjssjspppwCwswC第七章第七章 背包问题背包问题Proof :1、因为、因为 KP 中中 xs 不能取分数，不能取分数， 所以，所以，KP 的最优解一定是的最优解一定是 情形之一情形之一 .01ssxorx当当 ,0sx 由由 Th 2.1 可知，可知， 是此情形的上界是此情形的上界 ； 0U当当 ,1sx 这时，若这时，若1211sxxx重量超出重量超出 ,swC而此时价值密度值最小的是而此时价值密度值最小的是 .11ssp

13、w是此情形的上界是此情形的上界 .1U从而从而 是是 的上界的上界 .012max,()UUUz KP2 2 背包问题的分支定界法背包问题的分支定界法1w1swCsw11sjjCCwswCswC2、要证要证 ，只需，只需证证21UU0111UUand UU是显然的是显然的；01UU1111011111ssjjsssjjssssspUpCwpUpCwppCCwwC(KP) 的最优解值的最优解值11( ()ssoptjjspzC KPpCw1()(*)ssjsjsppwCwC(KP) 当当 的最优解值的最优解值1sx 111()(*)ssjsjsppwCw11,sssssppwCww1111()(

14、)ssssjsjsjjsspppwCpwCww11UU从而从而21.UU一般给出的上界越小，计算量越大，但越容易被剪枝一般给出的上界越小，计算量越大，但越容易被剪枝 .第七章第七章 背包问题背包问题 书上给出了两类分支定界法书上给出了两类分支定界法 (广探法、深探法广探法、深探法) ，实质是按什么条件来选结点进行分支，分支是对具有实质是按什么条件来选结点进行分支，分支是对具有最大价值密度的物品进行最大价值密度的物品进行 . 如下介绍的方法是参照确如下介绍的方法是参照确定定 U2 的思想，对关键项进行分支的思想，对关键项进行分支 .Example 1用分支定界法求如下用分支定界法求如下 KP :

15、770,20,39,37,7,5,1031,10,20,19,4,3,650jjnpwCSolution :可验证可验证7020391031102060K3K2K1K4K091,1,0,0,0,020 x 107u 30 x 31x 39 9702010720u230,0,1,0,0,0,031106xu191,1,0,0,0,019107xu40 x 41x 311,1,0,0,1,1,3105xu41,0,0,1,0,0,0107xu*max1,0,0,1,0,0,0107optxzGo back3 3 背包问题的近似算法背包问题的近似算法 通过前面介绍的通过前面介绍的 C (KP) ，自

16、然想到如下贪婪算法自然想到如下贪婪算法(Greedy Algorithm):111,0ssnxxxx其目标函数值为其目标函数值为 .11sjjp有改进的吗？有改进的吗？GA0step 10001xwkstep 210kjjkjw xwC若若 ,则则 ，1kx 否则否则 ；0kx step 3若若 则结束则结束;,kn:1,kk否则否则2 .step转转GA0是近似是近似算法吗？算法吗？第七章第七章 背包问题背包问题构造例子构造例子 I :11222,1,1,.npwpkwkCk 按上述算法，得按上述算法，得：0121,0,( )1;GAxxzI 为充分小的正数为充分小的正数 .而显然最优解为而

17、显然最优解为：120,1,( ).optxxzIk0( )10()( )GAoptzIkzIk 说明说明 GA0 的绝对性能比不会大于任意给定的正数的绝对性能比不会大于任意给定的正数,所以，它不能作为近似解所以，它不能作为近似解 . 但稍加改进，就可得到一但稍加改进，就可得到一个绝对性能比为常数的较好的近似算法个绝对性能比为常数的较好的近似算法 .3 3 背包问题的近似算法背包问题的近似算法GA1step 1step 2求解求解 C(KP)，得关键项记为，得关键项记为 s ;取取 作为近似解值作为近似解值 .11max,sjsjpp即若即若 ，则，则11sjsjpp111,0ssnxxxx否则

18、否则1110,1ssnsxxxxxExample 243,7,17,20 ,1,3,8,1011jjnpwCSolution :显然，物品显然，物品3 为关键项（即为关键项（即 s = 3）易验证易验证37172013810123710,pp而而317p 近似解为近似解为112430,1;17GAxxxxz有改进的吗？有改进的吗？用用 GA1 求如下求如下 KP :第七章第七章 背包问题背包问题GA2step 1求解求解 C(KP)，得关键项记为，得关键项记为 s ;step 2令令 maxijjpp若若11sjijpp111,0ssnxxxx则则否则否则1110,1iinixxxxxExam

19、ple 343,7,17,20 ,1,3,8,1011jjnpwC用用 GA2 求如下求如下 KP :Solution :123710,pp而而 4max20jjpp212340,1;20GAxxxxz 近似解为近似解为Theorem 2.311.2GARproof11( )sup1( )GAGAIoptzIRrrzI3 3 背包问题的近似算法背包问题的近似算法Theorem 2.421.2GAR证明与证明与 Th 2.3 的类似的类似 .对对Ex . 343,7,17,20 ,1,3,8,1011jjnpwC考虑对考虑对 GA2 进行修改，进一步可取进行修改，进一步可取14231,0 xxx

20、x则则23z 这在实际计算中是会有好处的这在实际计算中是会有好处的 . 但绝对性能比不但绝对性能比不会改进会改进 .Go onTheorem 2.3 的证明的证明Proof :先证先证再说明不可改进再说明不可改进112GAR由由 s 的定义知：的定义知： 对于任意实例对于任意实例 I11( )soptjsjzIpp111111( )max,()2ssGAjsjsjjzIpppp又又因此因此，1( )1( )2GAoptzIzI从而从而112GAR取实例取实例 I：113,1,1,npw 为充分小的正数为充分小的正数 .2323,2ppwwkCk1123( )1,1,0GAzIkxxx 123(

21、 )2 ,0,1optzIkxxx1( )11()( )22GAoptzIkkzIk则则112GAR从而从而112GAR第七章第七章 背包问题背包问题3 3 背包问题的近似算法背包问题的近似算法 已知已知 GA0 对解对解 0-1 背包问题效果很差，但在一般背背包问题效果很差，但在一般背包问题中却是可以的包问题中却是可以的 .设设 11max. .0 ,1njjjnjjjjzp xstw xCxzjn显然，显然，121,0nCxxxw是一个可行解是一个可行解 .011GACzpw通过求解通过求解 C(KP) 得得11( )optCzIpw松弛问题的最优解值松弛问题的最优解值01111( )1(

22、 )21GAoptCCzIwwCzICww012GAR进一步可证进一步可证012GAR1212:3 ,220,IpkpkkkwwCk第七章第七章 背包问题背包问题1975年年 Sahni 给出一个多项式时间近似算法给出一个多项式时间近似算法 .算法算法Sk :step 1对任意满足对任意满足1,2,MNnMk且且 的子集的子集 M ， ii MwC先将先将 M 中的物品放入包内中的物品放入包内,然后用算法然后用算法 GA1 或或 GA2 求解一个如下定义的求解一个如下定义的 KP ：物品集为物品集为 NM ，包容量为包容量为 ，ii MCw将得到的解与将得到的解与M 的并作为原问题的近似解的并

23、作为原问题的近似解 .step 2取上述所有不同解中最好一个作为输出取上述所有不同解中最好一个作为输出 .Theorem 2.511kSRk 计算复杂计算复杂性性1()kO kn证略证略 参见其他资料参见其他资料3 3 背包问题的近似算法背包问题的近似算法Theorem 2.6 如果如果 ，则背包问题不存在满足下，则背包问题不存在满足下述性质的多项式时间算法述性质的多项式时间算法 A :PNP 存在固定的正整数存在固定的正整数 K 使得对任意的实例使得对任意的实例 I 有有( )( ).AoptzIzIKProof : 用反证法，假定存在，则可证明算法用反证法，假定存在，则可证明算法 A 可在

24、多项式内可在多项式内精确地解精确地解 KP，但，但 KP 是是NP-C 的，这与的，这与 矛盾矛盾 .PNP 给定给定 KP 任一实例任一实例 I ，将物品，将物品 j 的价值换成的价值换成 (K+1)pj, 而重量而重量wj 不变，包的容量不变，由此得到一个新的实例不变，包的容量不变，由此得到一个新的实例 I . 显然由显然由 I 构造构造 I 是在多项式时间内完成的是在多项式时间内完成的 . 用用 A 解解 I 得到的解，也是得到的解，也是 I的一个可行解的一个可行解 . 算法算法A: I I, 用算法用算法 A 解解I,得到得到 I 的可行解的可行解 . 算法算法 A是多项是多项式时间算

25、法式时间算法 由于由于 I 与与 I 有相同的可行解集，有相同的可行解集，I 的任一可行解值是的任一可行解值是 I 的的同一可行解值的同一可行解值的 （K+1）倍，所以）倍，所以1( )( )( )( ) .1AoptAoptzIzIzIzIK( )( ),AoptzIzIK由假设知( )( )1.1AoptKzIzIK所以 由于由于 KP 任一可行解值为正整数，因此任一可行解值为正整数，因此 z A (I) = zopt (I)，这说明，这说明 A 总能得到实例总能得到实例 I 的最优的最优解，正是所需要的矛盾解，正是所需要的矛盾.Go back一、有界背包问题一、有界背包问题0-1 背包问

26、题背包问题：01 ;jxor一般背包问题一般背包问题： 0;jxz（无界背包问题）（无界背包问题）有界背包问题有界背包问题：0jjjxbb为给定的正整数为给定的正整数 .( Bounded Knapsack Problem )显然，显然，GKP 可化为可化为 BKP，只需令，只需令jjCbwBKP 可化为等价的可化为等价的 0-1 KP思想思想：任一整数可用任一整数可用 0 , 1 变量来表示，如变量来表示，如 非负整数非负整数16x231234222xxxxx如如 1312341,0,1,1xxxx第七章第七章 背包问题背包问题Theorem 2.7记记11min,jsiijjijsjbwCCCb w则则（1） 是是 BKP 的一个上界的一个上界 ；111s