第二章 背包问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息处理中的组合优化,第二章 背包问题,Combinatorial Optimization in Information Processing,第二章 背包问题,1,背包问题的描述,2,背包问题的分支定界法,3,背包问题的近似算法,4 0-1,背包问题的一些相关问题,第二章 背包问题,背包问题,(,Knapsack Problem,),是一个有着广泛应,用的组合优化问题，它不仅在投资决策、装载、库存等,方面有应用，而且常以子问题形式出现在大规模优化问,题中，它的理论与算法具有一定的代表性,.,1,背包问题的描述,背包问题的一般描述为：设有物品集,是一个准备放入容量为,的背包中的,n,项物品的集,合,.,物品 的重量为,价值为,如何选择,U,中的一些物品装入背包，使这些物品的,总重量不超过,C,，且使总价值达到最大？,1,背包问题的描述,背包问题的数学模型：,重量,价值,容量,因为决策变量,所以也称,0-1,背包问题,.,一般背包问题,:,(,G,eneral,K,napsack,P,roblem,),第二章 背包问题,为讨论方便，总可假定（相当于标准化）：,即按价值密度从大到小排列,.,实际问题并非满足,1,背包问题的描述,对,4,只需,O,(,nln,n,),次运算即可；,对,3,若,，,最优解为,;,对,2,若 ，则最优解中 事先可去掉,;,对,1,分三种情况讨论,:,(1),若 且,令,此时，最优解中,所以，该物品事先可去掉,;,(2),若 且,令,此时，最优解中,所以，该物品事先可去掉,;,容量取,第二章 背包问题,(3),若 且,令,只需在模型中，令 ，则系数即为大于零了,.,综上，对不满足（,1,）、（,2,）、（,3,）的假定，可,作如下处理，使之满足：,对 令,对 令,则原问题化为：,1,背包问题的描述,如果在（,KP,）中，令,令,该问题的实际意义,是求不放在包中的物,品的价值和最小,.,模型的意义,Go back,第二章 背包问题,2,背包问题的分支定界法,分支定界法,(,B,ranch and,B,ound,M,ethod,),的基本,思想在运筹学课程中已介绍，它的重要在于它提出了一,类新的思路（隐枚举法），使得许多原来不好解决的问,题有了解决的可能性。（具有普适性）,确定问题（子问题）的最优值的,界,极大（小）化问题,上（下）界,通常是通过求解松弛问题，用松弛问题的解作为界,Note,:,松弛问题选择的,原则,1,、松弛问题要与原问题的最优值尽量接近；,2,、,松弛问题要尽量容易解,.,这两个原则不易统一，所以可选择不同的松弛问题,2,背包问题的分支定界法,划分方法的选择,原则是希望分出来的子问题容易被查清，可加快计算,.,选哪个活问题先检查,1,、,先检查最大上界（极大化问题）的活问题,优点：,检查子问题较其他规则为少；,缺点：,计算机储存量较大,.,2,、,先检查最新产生的最大上界的活问题,优点：,计算机储存量较少；,缺点：,需要更多的分支运算,.,选择的不同，提供了发挥的余地,第二章 背包问题,考虑,KP,的松弛问题,：,C,(,KP,),如何求解？,思路：将物品按价值密度从大到小的顺序放入包内,记,关键项,第一个放不下的,物品的序号,?,Theorem,2.1,2,背包问题的分支定界法,C,(,KP,),最优解为,其中,最优解值为,proof,显然，,由于 的整数性，,得到,z,(,KP,),的一个上界：,表示不超过 的最大整数,.,Go on,Go back,第二章 背包问题,Theorem,2.1,的证明,显然,C,(,KP,),的最优解必满足,设 是其最优解，,要证,若存在 使,则至少存在 使,.,取充分小的,(,满足,:),将 增加 减少,此时,仍是一个可行解,且目标函数值增加,矛盾,.,同理可证,又由极大性知：,因此，是最优解,.,Proof,:,2,背包问题的分支定界法,Theorem,2.2,设,其中 与 定义同前,.,则,的一个上界为 ；,2,、,对背包问题任一实例，,.,作为上界,U,2,比,U,1,更好,第二章 背包问题,Proof,:,1,、因为,KP,中,x,s,不能取分数，,所以，,KP,的最优解一定是 情形之一,.,当,由,Th,2.1,可知，是此情形的上界；,当,这时，若,重量超出,而此时价值密度值最小的是,.,是此情形的上界,.,从而 是 的上界,.,2,背包问题的分支定界法,2,、,要证 ，只需证,是显然的,；,C,(,KP,),的最优解值,C,(,KP,),当 的最优解值,从而,一般给出的上界越小，计算量越大，但越容易被剪枝,.,第二章 背包问题,书上给出了两类分支定界法,(,广探法、深探法,),，,实质是按什么条件来选结点进行分支，分支是对具有,最大价值密度的物品进行,.,如下介绍的方法是参照确,定,U,2,的思想，对关键项进行分支,.,Example,1,用分支定界法求如下,KP,:,Solution,:,可验证,*,*,*,Go back,3,背包问题的近似算法,3,背包问题的近似算法,通过前面介绍的,C,(,KP,),，,自然想到如下贪婪算法,(,G,reedy,A,lgorithm,):,其目标函数值为,.,有改进的吗？,GA,0,step,1,step,2,若,则 ，,否则 ；,step,3,若 则结束,;,否则,转,GA,0,是近似,算法吗？,第二章 背包问题,构造例子,I:,按上述算法，得,：,为充分小的正数,.,而显然最优解为,：,说明,GA,0,的绝对性能比不会大于任意给定的正数,所以，它不能作为近似解,.,但稍加改进，就可得到一,个绝对性能比为常数的较好的近似算法,.,3,背包问题的近似算法,GA,1,step,1,step,2,求解,C,(,KP,),，得关键项记为,s,;,取 作为近似解值,.,即若 ，则,否则,Example,2,Solution,:,显然，物品,3,为关键项（即,s,=3,）,易验证,而,近似解为,有改进的吗？,用,GA,1,求如下,KP,:,第二章 背包问题,GA,2,step,1,求解,C,(,KP,),，得关键项记为,s,;,step,2,令,若,则,否则,Example,3,用,GA,2,求如下,KP,:,Solution,:,而,近似解为,Theorem,2.3,proof,3,背包问题的近似算法,Theorem,2.4,证明与,Th,2.3,的类似,.,对,Ex.,3,考虑对,GA,2,进行修改，进一步可取,则,这在实际计算中是会有好处的,.,但绝对性能比不,会改进,.,Go on,Theorem,2.3,的证明,Proof,:,先证,再说明不可改进,由,s,的定义知：,对于任意实例,I,又,因此,，,从而,取实例,I,：,为充分小的正数,.,则,从而,第二章 背包问题,3,背包问题的近似算法,已知,GA,0,对解,0-1,背包问题效果很差，但在一般背,包问题中却是可以的,.,设,显然，,是一个可行解,.,通过求解,C,(,KP,),得,松弛问题的最优解值,进一步可证,第二章 背包问题,1975,年,Sahni,给出一个多项式时间近似算法,.,算法,S,k,:,step,1,对任意满足,且 的子集,M,，,先将,M,中的物品放入包内,然后用算法,GA,1,或,GA,2,求解一个如下定义的,KP,：,物品集为,N,M,，,包容量为 ，,将得到的解与,M,的并作为原问题的近似解,.,step,2,取上述所有不同解中最好一个作为输出,.,Theorem,2.5,计算复杂性,证略 参见教材,p,99,3,背包问题的近似算法,Theorem,2.6,如果 ，则背包问题不存在满足下,述性质的多项式时间算法,A,:,存在固定的正整数,K,使得对任意的实例,I,有,Proof,:,用反证法，假定存在，则可证明算法,A,可在多项式内,精确地解,KP,，但,KP,是,NP-C,的，这与,矛盾,.,给定,KP,任一实例,I,，将物品,j,的价值换成,(,K,+1),p,j,而重量,w,j,不变，包的容量不变，由此得到一个新的实例,I.,显然由,I,构造,I,是在多项式时间内完成的,.,用,A,解,I,得到的解，也是,I,的一个可行解,.,算法,A,:I I,用算法,A,解,I,得到,I,的可行解,.,算法,A,是多项式时间算法,由于,I,与,I,有相同的可行解集，,I,的任一可行解值是,I,的,同一可行解值的（,K,+1,）倍，所以,由于,KP,任一可行解值为正整数，因此,z,A,(I)=,z,opt,(I),，这说明,A,总能得到实例,I,的最优,解，正是所需要的矛盾,.,Go back,4 0-1,背包问题的一些相关问题,一、有界背包问题,0-1,背包问题,：,一般背包问题,：,（无界背包问题）,有界背包问题,：,为给定的正整数,.,(,B,ounded,K,napsack,P,roblem,),显然，,GKP,可化为,BKP,，只需令,BKP,可化为等价的,0-1,KP,思想,：,任一整数可用,0,1,变量来表示，如 非负整数,如,13,第二章 背包问题,Theorem,2.7,记,则,（,1,）,是,BKP,的一个上界；,（,2,）,取,得到一个可行解，将此解的值与,b,s,p,s,的值比较,取大者为输出,.,该算法的绝对性能比,计算复杂性为,与前面讨论一样，总可假定 都是正整数,;,4 0-1,背包问题的一些相关问题,二、子集和问题,在组合优化问题中，很多问题是相通的，参数稍作,修正，可能就是另一个问题,.,在,0-1,背包问题中，令,(,这时,),即,称为子集和问题,S,ubset,S,um,P,roblem,SSP,是,0-1,KP,的特殊情形，所以原方法皆可用,.,但,因其特殊，它应有更简单的方法,.,第二章 背包问题,1,、,贪婪算法,(,GA,),：,按任意顺序将物品逐个放入包内，直到放不下为,止，然后将其结果与最大重量的物品比较，取优者为,输出,.,可证,计算复杂性为,O,(,n,).,2,、,近似算法,MTGS,:,4 0-1,背包问题的一些相关问题,将上述的贪婪算法分别用于物品集,取最好者为输出,.,这里假定,可证,计算复杂性为,O,(,nlogn,+,n,2,)=,O,(,n,2,).,第二章 背包问题,完,对如下背包问题,I,：物品数,n,=8,，背包容量,C,=60,价值（,p,1,，,p,2,，,，,p,8,）,=,（,85,，,26,，,39,，,37,，,112,，,5,，,10,，,15,）,重量（,w,1,，,w,2,，,，,w,8,）,=,（,41,，,13,，,20,，,19,，,59,，,3,，,7,，,12,）,1,、选择,GA,1,或,GA,2,求,I,的近似解；,2,、用分支定界法求解,I,。,练习：,