第3章动态规划3-4节-0-1背包问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,3.4 0-1,背包问题,第,3,章 动态规划,(Dynamic Programming).,1,0-1,背包问题,给定,n,种物品和一背包。物品,i,的重量是,w,i,，其价值为,v,i,，背包的容量为,C,。问,:,应如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,0-1,背包问题,描述,:,给定,c 0,w,i,0,v,i,0 , 1,i,n.,要求找一,n,元向量,(x,1,x,2,x,n,), x,i,0,1, ,w,i,x,i,c,且,v,i,x,i,达最大,.,即,一个特殊的整数规划问题。,2,1.,最优子结构,(,最优性原理,),最优性原理,:,设,(y,1,y,2,y,n,),是,(3.4.1),的一个最优解,.,则,(y,2,y,n,),是下面相应子问题的一个最优解,:,证明,:,使用反证法,.,若不然,设,(z,2,z,3,z,n,),是上述子问题的一个最优解,而,(y,2,y,3,y,n,),不是它的最优解,.,显然有,v,i,z,i,v,i,y,i,(i=2,n),且,w,1,y,1,+,w,i,z,i,c,因此,v,1,y,1,+,v,i,z,i,(i=2,n) ,v,i,y,i, (i=1,n),说明,(y,1,z,2, z,3,z,n,),是,(3-4-1)0-1,背包问题的一个更优解,导出,(y,1,y,2,y,n,),不是背包问题的最优解,矛盾,.,3,2.,递归关系,设所给,0-1,背包问题的子问题,的最优值为,m(i,，,j),，即,m(i,，,j),是背包容量为,j,，可选择物品为,i,，,i+1,，,，,n,时,0-1,背包问题的最优值。由,0-1,背包问题的最优子结构性质，可以建立计算,m(i,，,j),的递归式,:,4,注,:,(,3-4-3),式,此时,背包容量为,j,，可选择物品为,i,。,此时在对,x,i,作出决策之后,问题,处于两种状态之一,:,背包剩余容量是,j,没产生任何效益,;,剩余容量,j-w,i,效益值增长了,v,i,.,从,n,推至,i+1,i,算出最优值,m(i,j,),（,i=n,1,） 。,m(1,c),为最优值。,然后用回溯法,Traceback,找出最优解,x,i,其中,i,，,c,为整值。,3.,算法复杂度分析：,从,m(i,，,j),的递归式容易看出，算法,Knapsack,需要,O(nc,),计算时间,;,Traceback,需,O,（,n,）计算时间,；,算法总体需要,O(nc,),计算时间。,当背包容量,c,很大时，算法需要的计算时间较多。例如，当,c2,n,时，算法需要,(,n2,n,),计算时间。,5,4.,算法描述,template,void Knapsack( Type v,int,w,int,c,int,n, Type *m),int,jMax,=,min(wn,1, c,),/,背包剩余容量,/,for(int,j = 0; j=,jMax,; j+),/,背包不同剩余容量,j,jMax,c/,mnj,=0;,for(int,j=,wn,; jc/,mnj,=,vn,;,for(int,i=n-1; i1; i-),jMax,=min(wi-1, c);,for(int,j=0; j=,jMax,; j+),/,背包不同剩余容量,j,jMax,c/,mij,=mi+1j;,/,没产生任何效益,/,for(int,j=,wi,; jc/,mij,=max(mi+1j, mi+1j-wi+vi);,/,效益值增长,v,i,/,背包问题的动态规划算法,Knapsack,如下：,6,4.,算法描述,m1c=m2c;,if(c,=w1),m1c=max(m1c, m2c-w1+v1);,Template ,/,求最优解,x,i,/,void,Traceback(Type,*m,int,w,int,c,int,n,int,x),for(int,i=1; in; i+),if(mic,=mi+1c),xi,=0;,else ,xi,=1;,c= c-,wi,; ,xn,=(mnc)?1:0;,说明,:,当,w,i,为正整数时，用二维数组,m,来存储,m(i,j,),相应的最优值。,Knapsack,算法,的另一缺点是要求所给物品的重量,w,i,（,1,i,n,）,是整数,7,5,改进算法,PP.71PP.72,为克服以上缺点，引入阶梯函数。利用序偶概念，改进算法的计算时间复杂性为,O,（,2,n,）。而当所给物品的重量,w,i,是整数时，其计算时间复杂性为 （略） 。,动态规划的其他应用实例（略）,旅行商问题,矩阵连乘问题,系统可靠性设计,流水线调度问题,设备更新问题,最优二叉搜索树,图像压缩,8,动态规划缺陷,：,（,1,）,无一统一标准模型可供应用。利用“最优性原理”得出递归关系式后，必须结合问题的特点，结合其他数学技巧求解，且无统一处理方法。,（,2,）,数值求解中，当问题中的状态变量个数太多（如有向图中的边数），由于计算机存储量及计算速度限制而无法对付“维数障碍”。,由前述可知，任一多阶段决策过程中的最优化问题，都可以用非线性规划方法（,Nonlinear programming Methods,，特殊：,linear programming,）模型来描述。,动态规划的优越之处,:,（,1,）,易于确定全局解。动态规划方法是一种逐步改善的方法，它把原问题化成一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少的多，约束集合也简单得多，故较易于确定全局最优。特别当处理离散类型问题时，动态规划是求出全局最优化解的唯一方法。,（,2,）,能得一族解，有利分析结果是否有用或进行选择（决策），且大大节省工作量。,（,3,）,能利用经验，提高求解效率。动态规划方法反映过程逐段演变的前后联系，与实际进程更紧密，因而在计算中能,（,4,）,有广泛应用背景（略）,9,5.,算法改进,由,m(i,j),的递归式容易证明，在一般情况下，对每一个确定的,i(1in),，函数,m(i,j),是关于变量,j,的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数,m(i,j),由其全部跳跃点惟一确定。如图所示。,对每一个确定的,i(1in),，用一个表,pi,存储函数,m(i,，,j),的全部跳跃点。表,pi,可依计算,m(i,，,j),的递归式递归地由表,pi+1,计算，初始时,pn+1=(0,，,0),。,10,典型,例子,（,一）,n=3,，,c=6,，,w=4,，,3,，,2,，,v=5,，,2,，,1,。,x,(0,0),m(4,x),x,(2,1),m(4,x-2)+1,x,(0,0),(2,1),m(3,x),(3,2),x,m(3,x-3)+2,(5,3),x,(0,0),(2,1),m(2,x),(3,2),(5,3),x,m(2,x-4)+5,(4,5),(6,6),(7,7),(9,8),x,(0, 0),(2, 1),m(1,x),(3,2),(5,3),(4,5),(6,6),(7,7),(9,8),x,(0,0),(2,1),m(3,x),x,(0,0),(2,1),m(2,x),(3,2),(5,3),11,5.,算法改进,函数,m(i,j),是由函数,m(i+1,j),与函数,m(i+1,j-wi)+vi,作,max,运算得到的。因此，函数,m(i,j),的全部跳跃点包含于函数,m(i+1,，,j),的跳跃点集,pi+1,与函数,m(i+1,，,j-wi)+vi,的跳跃点集,qi+1,的并集中。易知，,(s,t),qi+1,当且仅当,wi,s,c,且,(s-wi,t-vi),pi+1,。因此，容易由,pi+1,确定跳跃点集,qi+1,如下,qi+1=pi+1,(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j),pi+1,另一方面，设,(a,，,b),和,(c,，,d),是,pi+1,qi+1,中的,2,个跳跃点，则当,c,a,且,db,时，,(c,，,d),受控于,(a,，,b),，从而,(c,，,d),不是,pi,中的跳跃点。除受控跳跃点外，,pi+1,qi+1,中的其他跳跃点均为,pi,中的跳跃点。,由此可见，在递归地由表,pi+1,计算表,pi,时，可先由,pi+1,计算出,qi+1,，然后合并表,pi+1,和表,qi+1,，并清除其中的受控跳跃点得到表,pi,。,12,典型,例子,（,二）,n=5,，,c=10,，,w=2,，,2,，,6,，,5,，,4,，,v=6,，,3,，,5,，,4,，,6,。,初始时,p6=(0,0),，,(w5,v5)=(4,6),。因此，,q6=p6,(w5,v5)=(4,6),。,p5=(0,0),(4,6),。,q5=p5,(w4,v4)=(5,4),(9,10),。从跳跃点集,p5,与,q5,的并集,p5,q5=(0,0),(4,6),(5,4),(9,10),中看到跳跃点,(5,4),受控于跳跃点,(4,6),。将受控跳跃点,(5,4),清除后，得到,p4=(0,0),(4,6),(9,10),q4=p4,(6,，,5)=(6,，,5),，,(10,，,11),p3=(0,，,0),，,(4,，,6),，,(9,，,10),，,(10,，,11),q3=p3,(2,，,3)=(2,，,3),，,(6,，,9),p2=(0,，,0),，,(2,，,3),，,(4,，,6),，,(6,，,9),，,(9,，,10),，,(10,，,11),q2=p2,(2,，,6)=(2,，,6),，,(4,，,9),，,(6,，,12),，,(8,，,15),p1=(0,，,0),，,(2,，,6),，,(4,，,9),，,(6,，,12),，,(8,，,15),p1,的最后的那个跳跃点,(8,15),给出所求的最优值为,m(1,c)=15,。,13,算法复杂度分析,上述算法的主要计算量在于计算跳跃点集,pi(1in),。由于,qi+1=pi+1,(w,i,，,v,i,),，故计算,qi+1,需要,O(|pi+1|),计算时间。合并,pi+1,和,qi+1,并清除受控跳跃点也需要,O(|pi+1|),计算时间。从跳跃点集,pi,的定义可以看出，,pi,中的跳跃点相应于,x,i,x,n,的,0/1,赋值。因此，,pi,中跳跃点个数不超过,2,n-i+1,。由此可见，算法计算跳跃点集,pi,所花费的计算时间为,从而，改进后算法的计算时间复杂性为,O(2,n,),。当所给物品的重量,w,i,(1in),是整数时，,|pi|c+1,，,(1in),。在这种情况下，改进后算法的计算时间复杂性为,O(minnc,2,n,),。,14,