背包和SubsetSum问题的近似解.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,背包问题的近似解,一、背包问题的数学描述,给定整数,C,和2个整数序列(,s,1,s,2,s,n,),(,p,1,p,2,p,n,),。s,1,s,2,s,n,以非递增的顺序排列。设,N=(1,2,n),为下标集,求：,受限于：,问题的简化版,给定整数,C,和整数序列(,s,1,s,2,s,n,)，,设(1,2,n),为下标集,求:,受限于：,二、背包问题的简单近似算法,sKnap,k,(C,S,take),int maxSum,sum;,indexSet,T=new,IndexSet,;,int,j;,take=,;,maxSum,=0;,for each subset TN with at most,k,elements:,sum=,iT,s,i,;,if(sum,C),for each j not in T:,if(sum+,s,j,C),sum+=,s,j,;,T=T,j,;,if(,maxsum,0,算法,sKnap,k,做,O(,kn,k,+1,),次运算；,sKnap,0,做,(,n),次运算。所以对,k,0,，,sKnap,k,P,证明：,N,包含,j,个元素的子集共有,C,n,j,个，所以外循环做,次运算。,因为,C,n,j,n,j,，,所以:,加上内循环的至多,n,次的,复杂性，算法的复杂性为,O(,k,n,k,+1,+n)。,定理13.13,定理：对,k0,R,sK,nap,k,(m),和,S,sK,nap,k,(n),在最坏情况下至多为1+1/,k。,设输入,I,为(,s,1,s,2,s,n,)，,opt(,I,)=m(,最优解情况下，背包内所含物体的,size,总和)。,若(,s,i,1,s,i,2,s,i,p,),是所得到的装填背包的最优解。,若,pk,则最优解也应在近似算法的范围内。,若,pk,则最优解,(,s,i,1,s,i,2,s,i,p,),以非递增的次序排列。,因为:,m=,s,i,1,+s,i,2,+,+s,i,p,1,jp,s,ij,m/j,s,i,(k+1),m/(k+1),1,jp,s,ij,m/j,根据近似算法，如果,j,是最优解中,k,之后第一个不能被加进,val,(,sKnap,k,(I),的,object:,val,(,sKnap,k,(I),+,s,j,Cm,val,(,sKnap,k,(I),m-,m/j,m-,m/(k+1),即：,近似解,mk,/(k+1),Rm/,mk,/(k+1)=1+1/k,