动态规划节背包问题

1、 1 2(3.4.1) max 1niiixvnixCxwtsiniii1,1 , 0 .1 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题描述:给定c 0, wi 0, vi 0 , 1in.要求找一n元向量(x1,x2,xn,), xi0,1, wi xic,且 vi xi达最大.即一个特殊的整数规划问题。 3 最优性原理最优性原理:设(y1,y2,yn)是 (3.4.1)的一个最优解.则(y2,yn)是下面相应子问题的一个最优解: niiixv2maxnixywCxwiniii2 ,1

2、, 0s.t 112 证明证明:使用反证法. 若不然,设(z2,z3,zn)是上述子问题的一个最优解,而(y2,y3,yn)不是它的最优解.显然有 vizi viyi (i=2,n)且 w1y1+ wizi c因此 v1y1+ vizi (i=2,n) viyi, (i=1,n) 说明(y1,z2, z3,zn)是(3-4-1)0-1背包问题的一个更优解,导出(y1,y2,yn)不是背包问题的最优解,矛盾. 4 设所给0-1背包问题的子问题(3.4.2) nikkkxvmax nkixjxwtsknikkk,.10 的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，

3、n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式:).(),(),(),(max),(343 0111iiiiwjwjjimvwjimjimjim (3.4.4) 00nnnwjwjvjnm ),( 5注注:(3-4-3)式此时背包容量为j，可选择物品为i。此时在对xi作出决策之后,问题处于两种状态之一:u背包剩余容量是j,没产生任何效益;u剩余容量j-wi,效益值增长了vi .从n推至i+1,i算出最优值m(i,j) （ i=n,1） 。 m(1,c)为最优值。然后用回溯法Traceback找出最优解xi 其中i，c为整值。)3 . 4 . 3(

4、 (2) 0(1) ), 1(), 1(), 1(max),(iiiiwjwjjimvwjimjimjim(3.4.4) (2) 0(1) 0),(nnnwjwjvjnm3.3.算法复杂度分析：算法复杂度分析：从m(i，j)的递归式容易看出，算法Knapsack需要O(nc)计算时间; Traceback需O（n）计算时间 ；算法总体需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要(n2n)计算时间。 6templatevoid Knapsack( Type v, int w, int c, int n, Type *m) int jMax = m

5、in(wn1, c) /背包剩余容量背包剩余容量/ for(int j = 0; j=jMax; j+) /背包不同剩余容量背包不同剩余容量j jMaxc/ 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 jMaxc/ mij=mi+1j; /没产生任何效益没产生任何效益/ for(int j=wi; jc/ mij=max(mi+1j, mi+1j-wi+vi); /效益值增长效益值增长vi / 背包问题

6、的动态规划背包问题的动态规划算法算法Knapsack如下：如下： 7 m1c=m2c; if(c=w1) m1c=max(m1c, m2c-w1+v1);Template /求最优解求最优解xi /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;说明说明:当wi为正整数时，用二维数组m来存储m(i,j)相应的最优值。Knapsack算法的另一算法的另一缺点是要求所给物品缺点是要求所给物品的重

7、量的重量w wi（1 i n）是整数是整数 8 为克服以上缺点，引入阶梯函数。利用序偶概念，改进算法的计算时间复杂性为O（2n ）。而当所给物品的重量wi是整数时，其计算时间复杂性为 （略） 。 动态规划的其他应用实例（略）旅行商问题矩阵连乘问题系统可靠性设计流水线调度问题设备更新问题最优二叉搜索树图像压缩(min,2 )nOnc 9 动态规划缺陷动态规划缺陷：（1）无一统一标准模型可供应用。利用“最优性原理”得出递归关系式后，必须结合问题的特点，结合其他数学技巧求解，且无统一处理方法。（2）数值求解中，当问题中的状态变量个数太多（如有向图中的边数），由于计算机存储量及计算速度限制而无法对付“

8、维数障碍”。 由前述可知，任一多阶段决策过程中的最优化问题，都可以用非线性规划方法（Nonlinear programming Methods，特殊：linear programming）模型来描述。 动态规划的优越之处动态规划的优越之处:（1）易于确定全局解。动态规划方法是一种逐步改善的方法，它把原问题化成一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少的多，约束集合也简单得多，故较易于确定全局最优。特别当处理离散类型问题时，动态规划是求出全局最优化解的唯一方法。（2）能得一族解，有利分析结果是否有用或进行选择（决策），且大大节省工作量。（3）能利用经验，提高求解效率。动态规划

9、方法反映过程逐段演变的前后联系，与实际进程更紧密，因而在计算中能（4）有广泛应用背景（略） 10由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)。 11n=3，c=6，w=4，3，2，v=5，2，1。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2

10、,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(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) 12函数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的并集中

11、。易知，(s,t)qi+1当且仅当wisc且(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+1qi+1中的2个跳跃点，则当ca且db时，(c，d)受控于(a，b)，从而(c，d)不是pi中的跳跃点。除受控跳跃点外，pi+1qi+1中的其他跳跃点均为pi中的跳跃点。由此可见，在递归地由表pi+1计算表pi时，可先由pi+1计算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳跃点得到表pi。 13n=5，c=10，w=2

12、，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的并集p5q5=(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。 14上述算法的主要计算量在于计算跳跃点集pi(1in)。由于qi+1=pi+1(wi，vi)，故计算qi+1需要O(|pi+1|)计算时间。合并pi+1和qi+1并清除受控跳跃点也需要O(|pi+