动态规划-0-1背包.ppt

数据结构实训,适用专业：软件工程（本科）学时：32,平顶山学院软件学院吕海莲 E-Mail：,实训3：动态规划-0-1背包问题,问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi(0,1)，此问题称为0-11背包问题,0-1背包问题,0-1背包问题是一个特殊的整数规划问题。可描述如下：,过程分析,背包的最大容量为10，那么在设置数组m大小时，可以设行列值为5和10，那么，对于m(i,j)就表示可选物品为in背包容量为j(总重量)时背包中所放物品的最大价值。,数据：物品个数n=5,物品重量wn=2，2，6，5，4,物品价值Vn=6，3，5，4，6,总重量c=10.,最优值过程分析,背包中的物品设为空，首先，我们先对物品n放入背包的情况做分析,即在总重量分别为0到10时,如何放置物品n,使总价值最大，此时要确定m(5,0.10)11个元素的值。,如果物品n的重量超过背包允许的总重量,则物品n不放入背包,此时背包中物品的总价值为0，否则，如果物品n装入背包后不超重，则装入物品n，此时背包的总价值为物品n的价值vn。,0 1 2 3 4 5 6 7 8 9 10 j,因w5=4,所以，当背包容量j小于w5时，物品5时不能放入的，所以当前的背包总价值都为0。当j=w5时，物品5可以放入背包，此时当前的背包总价值都为v5.,最优值过程分析,然后，我们在对物品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),最优值过程分析,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。,最优值过程分析,以此类推，完成m(4,6.10)的最优值,0 1 2 3 4 5 6 7 8 9 10 j,那么，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,最优值过程分析,填充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,最优值过程分析,填充m(2,0.10)的最优值,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,最优值过程分析,计算原问题的最优值,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,15)=15,依此计算m(1,0.9)的值,最优值过程分析,m的最终结果如下表,0 1 2 3 4 5 6 7 8 9 10 j,递归定义最优值,由前面的最优值过程分析实例，根据0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式：,构造最优解,我们可根据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，则j=j,否则，j=j-wi,此时i=i+1,然后我们重复上述两步，计算新一组(i,j)对应的xi值。直到i=n-1为止。,对物品n，直接由m(n,j)是否为0确定xn的值是0或1。,构造最优解,结果示例：,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,动态规划思想,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，为此，可以用一个表来记录所有已解决的子问题的答案而不管该答案是否用到，这就是动态规划的基本思想。,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。,1-最优子结构性质,最优子结构性质：动态规划算法的第一步是要刻画最优解的结构，即当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征,对于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,2-递归定义最优值,由前面的最优值过程分析实例，根据0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式：,动态规划算法分析：p72,3-计算最优值,根据前边的分析过程设计相应的算法，我们可从wn开始以自底向上的方式计算出最优值；完成m(1.n,0.c)的数据填充,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=max(m1c,m2c-w1+v1);,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;,背包中装入的重量和价值可以通过最优质求得。,实训2：设计要求,窗体设计基本要求：用户输入信息：物品个数、物品重量及价值、背包容量；输出信息：装入背包的物品序号、背包的总重量以及所装入物品的总价值。在此基础上扩展功能需求。,矩阵连乘,问题：设有给定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),矩阵连乘,多矩阵连乘满足结合律，假设给定三个矩阵A1,A2,A3的维数分别是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 不同组合方式下的乘运算次数是不相同的。,矩阵连乘,矩阵连乘问题即是对于给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。如何确定一个矩阵连乘积的最优的计算次序，是我们要解决的根本问题，通过传统的什么方法可以找出最优解？,穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,矩阵连乘,设有四个矩阵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,所以，穷举搜索法不是一个有效的算法。,下面介绍用动态规划法来解决最优计算次序问题。,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。,3.1 矩阵连乘问题,给定n个矩阵A1,A2,.,An，其中Ai与Ai+1是可乘的，i=1,2,.,n-1。考察这n个矩阵的连乘积A1A2.An。由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。,动态规划法1.分析最优解的结构,预处理：将矩阵连乘积AiAi+1.Aj简记为Ai:j，这里ij。考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为（AiAi+1.Ak）（Ak+1 Ak+2.Aj）。计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量。分析最优解的结构特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,2.建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n。当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n。当ij时，mi,j=mi,k+mk+1,j+pi-1pkpj，这里Ai的维数为pi-1pi。可以递归地定义mi,j为：k的位置只有j-i种可能。可以看出，在计算最优解mi,j时要从所有的断开处遴选，同时要依据较小规模时的最优解。,3.计算最优值,由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。,实例分析,过程分析：确定如下六个矩阵连乘的最优计算次序。p52,1.所有子问题最优解的数据存贮：由于不同子问题Ai:j(1ijn)的个数最多只有O(n2)，在计算过程中，为了保存已解决的子问题答案（最优解和断点）。我们可以设置两个二维表格m和s1.n1.n来存贮子问题的最优解。如下所示：,则：mij就表示子问题Ai:j即Ai Ai+1 Aj连乘的最优解sij就表示其子问题的断开位置,分解为两个最优子问题,实例分析,1.最小规模时的最优解，子问题间距(步长)step为1，即单矩阵，乘运算次数为0，矩阵加括号及最优解设置结果如下。,实例分析,2.计算子问题间距(步长)step为2的最优解。用到小于2时的子问题的最优解,当计算mij时，需要根据前边分析的递归关系来进行，把所有可能的断点都进行比较，选取最优的断点，并更新s的相应值,当step=2时，表示相邻矩阵之间加括号，所以要进行处理的中间断点k的变化次数都是1(递归公式中的i=kj)，我们先分析一般情形的加工算法,实例分析,3.递归公式中mi,j加工算法分析,当ij时,mij为Ai+1 Aj最优次数，sij为相应断点,mij=mii+mi+1j+pi-1*pi*pj;/初始化为Aisij=i;/设Ai为断点for(int k=i+1;k j;k+)/分别把Ai+1 Aj-1设为断点/这里Ai的维数为pi-1piint t=mik+mk+1j+pi-1*pk*pj;/Ak为断点if(t mij)mij=t;sij=k;,实例分析,4.step=2时的数据加工过程,mij=mii+mi+1j+pi-1*pi*pj;sij=i;/设Ai为断点for(int k=i+1;k j;k+)/这里Ai的维数为pi-1piint t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;,计算A1,2的过程:,i j mi,j si,j t,1 2 15750 1,矩阵维数数组p0.6:,30 35 15 5 10 20 25,初始化:,由于K=i+1=2=j,结束循环，m1,1=15750,计算其他四个子问题的过程:,与计算A1,2 相似，直接赋初始化的值35*15*5，15*5*10，5*10*20，10*20*25，,实例分析,4.所有step为2的子问题处理完毕后，数据结果如下：,实例分析,5.step=3时的数据加工过程,mij=mii+mi+1j+pi-1*pi*pj;sij=i;/设Ai为断点for(int k=i+1;k j;k+)/这里Ai的维数为pi-1piint t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;,计算A1,3的过程:,矩阵维数数组p0.6:,0 1 2 3 4 5 630 35 15 5 10 20 25,m 1,2 2,3 3,4 4,5 5,6 15750 2625 750 1000 5000S 1,2 2,3 3,4 4,5 5,6 1 2 3 4 5,计算A2,4的过程:,实例分析,5.step=3时的数据加工过程,mij=mii+mi+1j+pi-1*pi*pj;sij=i;/设Ai为断点for(int k=i+1;k j;k+)/这里Ai的维数为pi-1piint t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;,计算A3,5的过程:,矩阵维数数组p0.6:,0 1 2 3 4 5 630 35 15 5 10 20 25,m 1,2 2,3 3,4 4,5 5,6 15750 2625 750 1000 5000S 1,2 2,3 3,4 4,5 5,6 1 2 3 4 5,计算A4,6的过程:,实例分析,5.所有step为3的子问题处理完毕后，数据结果如下：,实例分析,6.继续增加step的值分别为4，5，6，按照相似的方法得出m和s数组的右上角的数据值。,实例分析,6.最后的结果如下：p52,示例结果,算法描述,算法描述：p51void MatrixChain(int*p，int n，int*m，int*s)/p存贮维数,pi-1和 pi代表Ai的维数,n为矩阵个数,m和s为最优次数和断点for(int i=1;i=n;i+)mii=0;/初始化for(int r=2;r=n;r+)/步长设置，分别计算2.n个矩阵组合的子问题for(int i=1;i=n-r+1;i+)/i为当前步长下的子问题个数,也表示子问题的序号，Ai则为子问题中的第/一个矩阵int j=i+r-1;/j为子问题中的最后一个矩阵序号，首位置+步长-1mij=mi+1j+pi-1*pi*pj;/初始化Ai为断点，前省略miisij=i;/设置Ai为断点 下面是计算AiAi+1.Aj 的最优值 for(int k=i+1;k j;k+)/把中间所有矩阵都作为断点分析一遍int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;,4.构造最优解,构造最优解：构造最优解是动态规划的第四步，如果需要求出问题的最优解，则必须执行第四步，前三步计算的最优值记录了更多的信息，在步骤四中可以根据前边的记录结果而快速构造出一个最优解。最优计算次数由m直接确定，而最优计算次序需要对s进行逆向断点追踪，由断点值把问题分解为计算两个子链的最优解，以此类推，直到原始点与断点重合为止。,