C语言----动态规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第十章 动态规划,用递推代替递归,用空间换时间,5/26/2026,1,10.1,什么是动态规划,1,、最短路径问题,2,、数塔问题,5/26/2026,2,7,E,5,2,D1,D2,3,7,3,8,C1,C2,C3,B1,B2,A,7,5,5,5,8,6,7,5,7,下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由,A-E,。,试用动态规划的最优化原理求出,A-E,的最省费用。,1,最短距离问题,5/26/2026,3,如图从,A,到,E,共分为,4,个阶段，即第一阶段从,A,到,B,，,第二阶段从,B,到,C,，,第三阶段从,C,到,D,，,第四阶段从,D,到,E,。,除起点,A,和终点,E,外，其它各点既是上一阶段的终点又是下一阶段的起点。,例如从,A,到,B,的第一阶段中，,A,为起点，终点有,B1,，,B2,两个，因而这时走的路线有两个选择，一是走到,B1,，一是走到,B2,。,若选择,B2,的决策，,B2,就是第一阶段在我们决策之下的结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。,在第二阶段，再从,B2,点出发，对于,B2,点就有一个可供选择的终点集合,(C1,，,C2,，,C3),；若选择由,B2,走至,C2,为第二阶段的决策，则,C2,就是第二阶段的终点，同时又是第三阶段的始点。,同理递推下去，可看到各个阶段的决策不同，线路就不同。,5/26/2026,4,很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短。,故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。如何解决这个问题呢？,要求在各阶段选取一个恰当的决策,5/26/2026,5,决策过程：,（,1,）由目标状态,E,向前推，可以分成四个阶段，即四个子问题。,D,E CE BE AE,（,2,）,策略：每个阶段到,E,的最省费用为本阶段的决策路径。,用动态规划法求解,5/26/2026,6,（,3,）,D1,，,D2,是第一次输入的结点。他们到,E,都只有一种费用：,f(D1)=5 f(D2)=2,E,5,2,D1,D2,目前无法定下，哪一个点将在全程最优策略的路径上。第二阶段计算中，,5,，,2,都应分别参加计算,5/26/2026,7,（,4,）,C1,，,C2,，,C3,是第二次输入结点，他们到,D1,，,D2,各有两种费用。此时应计算,C1,，,C2,，,C3,分别到,E,的最少费用。,f(C1)=minC1D1+f(D1),，,C1D2+f(D2),。,计算结果是,f(C1)=C1D1+f(D1)=8,（,D1),同理,C2,的决策路径计算结果是,C2+D2+E,f(C2)=7,。,同理,C3,的决策路径计算结果是,C3+D2+E,，,f(C3)=10,。,E,8,7,5,2,D1,D2,3,7,3,8,C1,C2,C3,5,7,10,5/26/2026,8,（,5,）第三次输入结点为,B1,，,B2,，,而决策输出结点可能为,C1,，,C2,，,C3,。,仿前计算可得,Bl,，,B2,的决策路径为如下情况。,Bl,:B1C1,费用,f(B1)=5+8=13,，,B2:B2C1,费用,f(B2)=6+8=14,，,7,5,B1,B2,5,8,6,7,E,8,7,5,2,D1,D2,3,7,3,8,C1,C2,C3,5,7,10,13,14,5/26/2026,9,（,6,）第四次输入结点为,A,，,决策输出结点可能为,B1,，,B2,。,同理可得决策路径为,A,：,AB2,，,费用,5+14=19,此时才正式确定每个子问题的结点中，那一个结点将在最优费用的路径上。,子问题的决策中，只对同一城市（结点）比较优劣。而同一阶段的城市（结点）的优劣要由下一个阶段去决定。,7,5,B1,B2,5,8,6,7,E,8,7,5,2,D1,D2,3,7,3,8,C1,C2,C3,5,7,10,13,14,A,19,7,5,5/26/2026,10,2,、数塔问题,有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。,5/26/2026,11,用,暴力,的方法，可以吗？,5/26/2026,12,这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如,31,），则需要列举出的路径条数将是一个非常庞大的数目（,230=10243 109=10,亿）。,试想一下：,5/26/2026,13,拒绝,暴力，,倡导,和谐,5/26/2026,14,从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。,可见，由下层的子问题可以得到上层的子问题，所以，可从底层开始，层层递进，最后得到最大值。,结论：自顶向下的分析，自底向上的计算。,考虑一下：,5/26/2026,15,如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够,保存已经解决的子问题的答案,，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的,基本思路是，用一个表记录所有已解决的子问题的答案,，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。,10.2,动态规划的基本思想,5/26/2026,16,动态规划的基本步骤,动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行：,5/26/2026,17,（,1,）找出最优解的性质，并刻画其结构特征。,（,2,）递归地定义最优值。,（,3,）以,自底向上,的方式计算出最优值。,（,4,）根据计算最优值时得到的信息，构造一个最优解。,其中（,1,）（,3,）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（,4,）可以省去。若需要求出问题的一个最优解，则必须执行步骤（,4,）。此时，在步骤（,3,）中计算最优值时，通常需记录更多的信息，以便在步骤（,4,）中，根据所记录的信息，快速构造出一个最优解。,基本步骤,5/26/2026,18,动态规划问题的特征,动态规划算法的有效性依赖于问题本身所具有的两个重要性质：,1,、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。,2,、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。,5/26/2026,19,10.3,最长有序子序列,I,0,1,2,3,4,5,6,7,8,NumI,1,4,7,2,5,8,3,6,9,5/26/2026,20,子问题的构造,子问题,“,求以,a,k,（,k=1,2,3N,）为终点的最长上升子序列的长度”,虽然这个子问题和原问题形式上并不完全一样，但是只要这,N,个子问题都解决了，那么这,N,个子问题的解中，最大的那个就是整个问题的解。,该子问题可以递推求解,5/26/2026,21,假定,MaxLen,(k),表示以,a,k,做为“终点”的最长上升子序列的长度，那么：,MaxLen,(1)=1,MaxLen,(k)=Max,MaxLen,(i),：,1i k,且,a,i,=cij-1,cij=ci-1j;,否则,cij=cij-1;,LCS(Xm,Yn,)=,LCS(Xm,Yn)+xm,5/26/2026,38,0,0,0,0,0,0,0,0,0,0,0,0,0,例：,X=A B C B D A B Y=B D C A B A,0 B D C A B A,0,A,B,C,B,D,A,B,A,AB,ABC,ABCB,ABCBD,ABCBDA,ABCBDAB,B BD BDC,5/26/2026,39,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,2,2,0,1,1,2,2,2,2,0,1,1,2,2,3,3,0,1,2,2,2,3,3,0,1,2,2,3,3,4,0,1,2,2,3,4,4,例：,X=A B C B D A B Y=B D C A B A,0 B D C A B A,0,A,B,C,B,D,A,B,5/26/2026,40,void,LCS,(int,m,，,int,n,，,char*x,，,char*y,char*z,int,*c),/,不用数组,b,，,构造最优解的非递归算法,int,i=m,j=n;,int,k=cmn;/,最长公共子序列的长度,while(i0&j0),if(xi=yj)zk-=xi;i-;j-;,else if(ci-1j=cij-1)i-;,else j-;,构造最长公共子序列,5/26/2026,41,10.5 0-1,背包问题,给定,n,种物品和一背包。物品,i,的重量是,w,i,，,其价值为,v,i,，,背包的容量为,C,。,问应如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,目标：使装入背包中物品的总价值最大,约束条件：装入的物品总重不得超过,C,5/26/2026,42,海盗盗宝问题,海盗有一背包，最大容积为,9,，现有,5,件宝物：体积,si,分别是,2,、,3,、,4,、,5,和,4,公斤,价值,vi,分别是,3,、,7,、,5,、,9,和,8,请给出装载方案，使背包价值达到最大。,S1=2,v1=3,S2=3,v2=7,S3=4,v3=5,S4=5,v4=9,S5=4,v5=8,C=9,5/26/2026,43,一,开始，见物品就装，物品,1,、,2,、,3,全装入，背包装满了，得到背包总价值为,15,，这是不是最大价值呢？,S1=2,v1=3,S2=3,v2=7,S3=4,v3=5,S4=5,v4=9,S5=4,v5=8,考虑只有前三个物品的情况,5/26/2026,44,物品,4,该不该装？有两个选择：,（,1,）不装，背包价值不变，为,15,S1=2,v1=3,S2=3,v2=7,S3=4,v3=5,S4=5,v4=9,（,2,）,装入，它占去的体积为,5,，得到价值为,9,，,剩下容积,4,最多可以装下多大价值？,考虑只有前,4,个物品的情况,5/26/2026,45,这是一个,n=3(,从前三个物品中选择），容量,c=4,的子问题。,目前最优：装入物品,2,和物品,4,，总价值为,16,若已知这个子问题的解是：,装物品,2,，得价值为,7,。,S1=2,v1=3,S3=4,v3=5,S4=5,v4=9,（,2,）,装入物品,4,，它占去的体积为,5,，得到价值为,9,，,剩下容积,4,最多可以装下多大价值？,S2=3,v2=7,5/26/2026,46,S1=2,v1=3,S3=4,v3=5,S4=5,v4=9,S5=4,v5=8,考虑,5,个物品的情况,S2=3,v2=7,物品,5,该不该装？,(1),不装，得到背包价值仍为,16,5/26/2026,47,（,2,）若装入物品,5,，占用体积为,4,，得价值为,8,，背包剩余容积为,5,。,如何在前,4,个物品中选择装入，使背包价值最大化？,这是,n=4,c=5,的一个子问题。,若得到该子问题的解为：,装入物品,1,、,2,，得价值为,10,S1=2,v1=3,S3=4,v3=5,S5=4,v5=8,考虑,5,个物品的情况,S2=3,v2=7,目前最优：装入物品,5,和,1,、,2,，总价值为,1816,S4=5,v4=9,5/26/2026,48,子问题的构造,当,n=1,时,:,只有一个物品，,s1=2,v1=3,若,背包容量,c=0,、,1,，,则无法装入物品,1,，得到背包价值为,0,若背包容量,c=2,、,3,、,4,、,5,、,6,，,7,，,8,，,9,则可装入物品,1,，得到背包价值为,3,。,C10=0 C11=0 C12=3 C13=3 C14=3 C15=3 C16=3 C17=3 C18=3 C19=3,5/26/2026,49,考虑两个物品的情况,当,n=2,时，有两个物品，,s1=2,v1=3,，,s2=3,v2=7,若,背包容量,c=0,、,1,，,得到背包价值为,0,若背包容量,c=2,，,可装入物品,1,，得总价值,m22=3,若背包容量,c=3,，,m23=7,若背包容量,c=4,m24=7,若背包容量,c=5,m25=10,若不,装,物品,2,，,m23=m13=3,若装入物品,2,，,m23=v2+m13-3=7+0=7,m26=10 m27=10,m28=10 m29=10,若不,装,物品,2,，,m25=m15=3,若装入物品,2,，,m25=v2+m15-3=7+3=7,5/26/2026,50,递推关系的建立,用,mij,来表示从前,i,个物品中选取物品装入容量为,j,的背包所得的最大价值。则要寻求的是,mnc,。,mij,是以下两个值的最大值（,1,）,mi-1j:,即不装入物品,i,背包价值与仅考虑前,i-1,个物品时情况相同；,（,2,）,vi+mi-1j-si:,即装入物品,i,再从前,i-1,个物品中选取，使背包剩余容积,j-si,价值最大化。,5/26/2026,51,构造价值数组,S1=2,v1=3,S2=3,v2=7,S3=4,v3=5,S4=5,v4=9,S5=4,v5=8,0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,1,0,2,0,3,0,4,0,5,0,背包容量,j,从前,i,个物品中选取,5/26/2026,52,S1=2,v1=3,S2=3,v2=7,S3=4,v3=5,S4=5,v4=9,S5=4,v5=8,0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,1,0,0,3,3,3,3,3,3,3,3,2,0,0,3,7,7,10,10,10,10,10,3,0,0,3,7,7,10,10,12,12,15,4,0,0,3,7,7,10,10,12,16,16,5,0,18,背包容量,j,从前,i,个物品中选取,5/26/2026,53,构造最优解,0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,1,0,0,3,3,3,3,3,3,3,3,2,0,0,3,7,7,10,10,10,10,10,3,0,0,3,7,7,10,10,12,12,15,4,0,0,3,7,7,10,10,12,16,16,5,0,0,3,7,8,10,11,15,16,18,因,m59m49,物品,5,被装入，剩余,c=9-s,5,=5,因,m45m35,物品,4,被装入，剩余,c=9-s,4,=0,5/26/2026,54,void,Knapsack(int,t,v,int,w,int,c,int,n,float,mN,),/,构造价值数组,m,int,i,j;,for(i,=0;i=n;i+)mi0=0;,for(j,=0;j=c;j+)m0j=0;,for(i,=1;n;i+),/,计算前,n-1,行,for(j,=1;j,wi,;j+),mij,=mi-1j;,for(j,=,wi,;j mi-1j),mij,=t;,else,mij,=mi-1j;,5/26/2026,55,/,计算最后一行的,mnc,t=,vn,+mn-1c-wn;,If(t mn-1c),mnc,=t,else,mnc,=mn-1c;,5/26/2026,56,思考：,免费馅饼,5/26/2026,57,如何解决？,子问题：最后,1,秒最多能接住几个，最后两秒、最后两秒,.,还与当时他站的位置有关子问题是二维的：,Tij,表示第,i,秒若站在位置,j,，从第,i,秒之后能接住多少个馅饼,5/26/2026,58,Tij,表示第,i,秒若站在位置,j,，从第,i,秒之后能接住多少个馅饼,Tij,:,若第,i+1,秒站在位置,j,，那么第,i,秒他可能到达的位置是,j-1,j,j+1,去那个位置接到馅饼最多？,T(i,j-1),Tij,=Ti+1j+max,T(i,j,),T(i,j+1),再考虑一下,j=0,和,j=10,的情况即可,5/26/2026,59,计算过程,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0 1 2 3 4 5 6 7 8 9 10,0,1,2,3,4,5,6,7,5/26/2026,60,0,0,0,0,4,0,0,0,0,0,0,0,0,0,1,1,4,3,3,0,0,0,0,0,0,0,0,0,3,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0 1 2 3 4 5 6 7 8 9 10,0,1,2,3,4,5,6,7,5/26/2026,61,课后任务：,一、,DIY,在线作业,(4):,2008ACM,ProgrammingExercise,（,4,）,_,动态规划,二、常规练习（包含以上作业）,1003,、,1466,、,1087,、,1159,、,1176,、,1058,、,1069,、,2059,、,2084,、,2151,5/26/2026,62,