《动态规划-0-1背包课件》由会员分享，可在线阅读，更多相关《动态规划-0-1背包课件（45页珍藏版）》请在金锄头文库上搜索。
1、数据结构实训,适用专业： 软件工程（本科） 学时： 32,平顶山学院软件学院 吕海莲 E-Mail：lvhailian_,2,实训3：动态规划-0-1背包问题,问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi(0,1)，此问题称为0-11背包问题,3,0-1背包问题,0-1背包问题是一个特殊的整数规划问题。可描述如下：,4,过程分析,背包的最大容量为10，那么在设置数组m大小时，可以设行列
2、值为5和10，那么，对于m(i,j)就表示可选物品为in背包容量为j(总重量)时背包中所放物品的最大价值。,数据：物品个数n=5,物品重量wn=2，2，6，5，4,物品价值Vn=6，3，5，4，6,总重量c=10.,5,最优值过程分析,背包中的物品设为空，首先，我们先对物品n放入背包的情况做分析,即在总重量分别为0到10时,如何放置物品n,使总价值最大，此时要确定m(5,0.10)11个元素的值。,如果物品n的重量超过背包允许的总重量,则物品n不放入背包,此时背包中物品的总价值为0，否则，如果物品n装入背包后不超重，则装入物品n，此时背包的总价值为物品n的价值vn。,0 1 2 3 4 5 6
3、 7 8 9 10 j,因w5=4,所以，当背包容量j小于w5时，物品5时不能放入的，所以当前的背包总价值都为0。当j=w5时，物品5可以放入背包，此时当前的背包总价值都为v5.,6,最优值过程分析,然后，我们在对物品5处理后的基础上，对物品4进行分析。此时我们的任务是要确定m(4,0.10)11个元素的值。用同样的方法，对物品4的处理有两种情况：w4大于j和w4小于j。,1.w4j，当背包容量j小于w4时，物品4时不能放入的，所以当前的背包总价值与4+1.n保持一致，即m(4,j)=m(5,j)。 即,0 1 2 3 4 5 6 7 8 9 10 j,m(4,0-4)=m(5,0-4),7,
4、最优值过程分析,2.当j=w4时，对物品4要么放入要么不放入，最优值的选择标准应依据总价值，总价值高的作为最优值。如：m(4,5),w4不放入时,原值，总价值是6=m(4+1,5),0 1 2 3 4 5 6 7 8 9 10 j,当w4放入时，则要配合其前边的最优值，即w4的放入，使剩余物品(4+1.n)的最大容量变为j-w4,此时背包中的最大容量为m(4+1,j-w4)的值0加上v4的值4，然后比较w4放入与否的总价值，因此m(4,5)选择w4不放入背包，最优值是依然是6。,8,最优值过程分析,以此类推，完成m(4,6.10)的最优值,0 1 2 3 4 5 6 7 8 9 10 j,那么
5、，m(4,7), m(4,8),m(4,9),m(4,10)的值分别为：,m( 5 , 6)=6,m( 5 , 6-5 )+ 4=4,m(4 , 6)=max(6,4)=6,i,j,i+1,j,i+1,j-wi,vi,6,6,10,10,9,最优值过程分析,填充m(3,1.10)的最优值,0 1 2 3 4 5 6 7 8 9 10 j,那么，m(3,0.10的值分别为：,m( i+1 , j ),m( i+1 , j-wi )+ vi,0:0,1:0,2:0,3:0,max,4:6,5:6,6: 6,7:6,8:6,9:10,10:11,10,最优值过程分析,填充m(2,0.10)的最优值,
6、0 1 2 3 4 5 6 7 8 9 10 j,那么，m(2,0.10）的值分别为：,m( i+1 , j ),m( i+1 , j-wi )+ vi,0:0,1:0,2:3,3:3,max,4:6,5:6,6: 9,7:9,8:9,9:10,10:11,11,最优值过程分析,计算原问题的最优值,0 1 2 3 4 5 6 7 8 9 10 j,c=10w1,所以，m(1,10)=max(m(2,10),m(2,c-w1)+v1),同样，如果w1大于c，则w1不放入，m( 1 ,c )=m(2,c)，否则，从放与不放的最大值中选择最优值。,=max(11,m(2,8)+6)=max(11,1
7、5)=15,依此计算m(1,0.9)的值,12,最优值过程分析,m的最终结果如下表,0 1 2 3 4 5 6 7 8 9 10 j,13,递归定义最优值,由前面的最优值过程分析实例，根据0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式：,14,构造最优解,我们可根据c列的数据来构造最优解，从i=1,j=c即m(i,j)开始，如果m(i,j)=m(i+1,j),则物品wi没有装入背包，从而xi=0，否则，物品wi装入背包，相应的xi=1，此时，为了确定其后继即k=i+1的xk的值，我们应在k行寻找新的j值作为参照。,0 1 2 3 4 5 6 7 8 9 10 j,如果xi=0
8、，则j=j,否则，j= j-wi ,此时i=i+1,然后我们重复上述两步，计算新一组(i,j)对应的xi值。直到i=n-1为止。,对物品n，直接由m(n,j)是否为0确定xn的值是0或1。,15,构造最优解,结果示例：,0 1 2 3 4 5 6 7 8 9 10 j,x1=1,j=j-wi=10-2=8,j= j-w2=6,x2=1,j=j=6,x3=0,j=j=6,x4=0,m( i , j)0,5, 6,6,x5=1,所以，原问题的最优解是(1,1,0,0,1),c=8,总价值=15,16,动态规划思想,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。 但是经分解
9、得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，为此，可以用一个表来记录所有已解决的子问题的答案而不管该答案是否用到，这就是动态规划的基本思想。,17,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。,18,1-最优子结构性质,最优子结构性质：动态规划算法的第一步是要刻画最优解的结构，即当问题的最优解包含了其子问题的最优解时，称该问题具有最
10、优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征,对于0-1背包问题，其最优子结构性质如下：,设(y1,y2,yn)是0-1背包问题的一个最优解，则(y2,y3,yn)则是下面相应子问题的一个最优解:,max,i=2,n,viyi,i=2,n,wiyi,c-w1y1,yi,0,1,2 i n,19,2-递归定义最优值,由前面的最优值过程分析实例，根据0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式：,动态规划算法分析：p72,20,3-计算最优值,根据前边的分析过程设计相应的算法，我们可从wn开始以自底向上的方式计算出最优值；完成m(1.n,0.c)的数
11、据填充,jmax=min(wn-1,c);/当前n物品不能装入的背包容量,for(j=0;j=jmax;j+)mnj=0;/背包容量小于wn时不装入,for(j=wn;j=c;j+) mnj=vn;/装入wn,只装入wn的初始化效果,利用递归定义自底向上计算最优值,m2.n,for(i=n-1;i1;i-),jmax=min(wi-1,c);wi不能装入的临界值 for(j=0;j=jmax;j+)mij=mi+1j ;/vi不能装入的容量,for(j=wi;j=c;j+)mij=max(mi+1j,mi+1j-wi+vi) ; ,m1c=m2c;,计算m11.c,if(c=w1) w1c=m
12、ax(m1c,m2c-w1+v1);,21,4-构造最优解,我们可根据c列的数据来构造最优解，从i=1,j=c即m(i,j)开始，如果m(i,j)=m(i+1,j),则物品wi没有装入背包，从而xi=0，否则，物品wi装入背包，相应的xi=1，此时，为了确定其后继即k=i+1的xk的值，我们应在k行寻找新的j值作为参照。对物品n，直接由m(n,j)是否为0确定xn的值是0或1,for(i=1;i=n;i+),if(mic=mi+1c) xi=0,else xi=1; c=c-wi;,if(mnc0) xn=1;else xn=0;,背包中装入的重量和价值可以通过最优质求得。,22,实训2：设计
13、要求,窗体设计基本要求：用户输入信息：物品个数、物品重量及价值、背包容量；输出信息：装入背包的物品序号、背包的总重量以及所装入物品的总价值。在此基础上扩展功能需求。,23,矩阵连乘,问题：设有给定n个矩阵A1,A2,.,An，其中Ai与Ai+1是可乘的，i=1,2,.,n-1。考察这n个矩阵的连乘积A1A2.An。 假设给定两个矩阵A1,A2, 它们的维数分别是m*n,n*p,则计算A1A2的标准算法怎样设计？,关标准算法中，主要计算量在三重循环，问总共需要多少次数乘？时间复杂度是多少？,P50,m*n*p，O(n3),24,矩阵连乘,多矩阵连乘满足结合律，假设给定三个矩阵A1,A2, A3的
14、维数分别是10*100，100*5，5*50， 问： A1,A2, A3有多少种组合方式，不同组合方式下各进行多少次数乘运算？,两种， (A1A2 ) A3 ) 和(A1 ( A2 A3 ) )， (A1A2 ) A3 )乘运算的次数为(10*100*5)+10*5*50=5000+2500=7500， (A1 ( A2 A3 ) )乘运算的次数为(100*5*50)+10*100*50=25000+50000=75000 不同组合方式下的乘运算次数是不相同的。,25,矩阵连乘,矩阵连乘问题即是对于给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连
15、乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 如何确定一个矩阵连乘积的最优的计算次序，是我们要解决的根本问题，通过传统的什么方法可以找出最优解？,穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,26,矩阵连乘,设有四个矩阵A,B,C,D，它们的维数分别是：A=5010，B=1040，C=4030，D=305 则总共有五种完全加括号的方式：(A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D)，其数乘次数分别为：16000, 10500, 36000, 87500, 34500,
16、所以，穷举搜索法不是一个有效的算法。,下面介绍用动态规划法来解决最优计算次序问题。,27,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。,28,3.1 矩阵连乘问题,给定n个矩阵A1,A2,.,An，其中Ai与Ai+1是可乘的，i=1,2,.,n-1。考察这n个矩阵的连乘积A1A2.An。 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。,29,动态规划法1.分析最优解的结构,预处理： 将矩阵连乘积AiAi+1.Aj简记为Ai:j，这里ij。 考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括
