(牛X)动态规划入门篇.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,*,动态规划入门篇,成都大学第二期,ACM,暑期集训,李明金,2009/08/12,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,1,前言,纵观,ACM,届，大到每年的全球总决赛，小到,TC,的,SRM,抑或各个,OJ,的月赛，我们很轻易的发现一个共同的规律,动态规划在其中稳稳的占据了一个重要的地位。,可以说，掌握了动态规划，不一定会成为大牛，但是一只大牛，是肯定精通动态规划的。,2009-8-12,成都大学,ACM,暑期集训DP,篇,李明金,2,动态规划，和分治法一样，是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分成一些独立的子问题，递归求解各子问题，然后合并子问题的解而得到原问题的解。于此不同，动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。动态规划对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。,动态规划通常应用于最优化问题。此类问题可能有许多种可行解。每个解都有一个值，而我们希望找到一个具有最优（最大或最小）值的解。称这样的问题为该问题的,“,一个,”,最优解（而不是,“,确定的,”,最优解），因为可能存在多个取最优解的值。,总结：自从有了动态规划，这个世界变得好美妙！,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,3,目录,0.,动态规划的基本步骤,1.,一个例题,2.,什么时候需要动态规划,3.,最优子结构,4.,重叠子问题,5.,动态规划的两个重要元素,状态,&,状态转移方程,6.,备忘录介绍,7.,例题,数字三角形,花束摆放 最大数字子串,积木游戏,Subsquence,炮兵阵地,(,状态压缩动态规划,),8.,练习,:NOJ,江苏省赛回放,C D E,（三角形演变题）,H,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,4,0.,动态规划的基本步骤,1,）描述最优解的结构,2,）递归定义最优解的值,3,）按自底向上的方式计算最优解的值,4,）由计算出的结果构造一个最优解,第,1-3,步构成问题的动态规划解的基础。第四步只要求计算最优解的值时可以略去。如果的确做了第四步，则有时要在第三步的计算中记录一些附加信息，使构造一个最优解变得容易。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,5,1.,一个例题,例一：装配线调度问题,描述,：某汽车工厂有,2,个装配线，每个装配线有,n,个装配站（按顺序编号,1,n,），两个装配线对应的装配站执行相同的功能，但所用的时间可能不同。经过第,i,条流水线（,i=1,，,2,）的第,j,个装配站所花的时间为,Aij,。从第,i,条流水线的第,j,个装配站移到第,j+1,个装配站的时间可以忽略，而移到另外一个流水线的下一个装配站则需要一定的时间,Tij,。,汽车进入流水线不需要花时间，出流水线时需要花时间,Tin,。,汽车的装配需要按顺序经过所有装配站。,现在已知装配时间,Aij,和转移时间,Tij,，要求输出装配一辆汽车所需要的最短时间。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,6,方案一：暴力搜索，穷举所有装配可能，然后选择极小。,显然这个方案是不可行的，因为我们分析可知，装配方式共有,2N,种（将所使用装配站一内的站看做一个集合，全集是,1.N,，子集就有,2N这时时间复杂度到达,O,（,2N,），显然,N,太大的时候是一定会,TE,的。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,7,方案二：动态规划。,步骤一：描述最优解的结构,在这里就是通过工厂最快路线的结构,其实这里就是描述问题是否具有一个最优子结构，即可以利用子问题的最优解构造原问题的一个最优解。,在这道题中，观察一条通过,S1,，,j,的最快路线，我们发现，它必然是通过,S1,，,j-1,或,S2,，,j-1,中的一个的最快路线（如果不是最快，则自我矛盾，,S1,，,j,就不是最快了）,为了解决这个问题，即寻找通过人一条装配线上的装配站,J,的最快路线，我们解决它的子问题，即寻找通过两条装配线上的装配站,J-1,的最快路线。,所以，对于这个问题，我们可以求子问题的最优解，从而得到原问题的最优解。,PS,：状态，状态转移方程的概念将会在理脱出，后面会提到，只要找好了状态方程（加元等手段），就能轻松使用动态规划。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,8,步骤二：一个递归的解,利用子问题的最优解来递归定义一个最优解的值。,在这个问题中，我们选择在两条装备线上通过装配站,j,的最快路线的问题作为子问题（,j=1,，,2,，,3.,，,n,）。令,fij,表示一个底盘从起点到装配站,Si,，,j,的最快可能时间。,我们的最终目标是确定底盘通过工厂的所有路线的最快时间，记做,f*,。,f*=min(f1n+x1,f2n+x2),下面的问题就是确定,f11,和,f21,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,9,显然，不管是从那条线路开始装配的，底盘肯定是直接到达装配站,1,的，也就是说之前是不用计算转移到装配站,1,的时间的。,则,f11=e1+a1,1,f21=e2+a2,1,现在计算,fij,，显然简单递推可知：,fi1=,ei,+ai,1;,fij,=min(fij-1+,ai,j,fij-1+ti,j-1+a2,j),fij,的值就是子问题的最优解的值。,注意：这里，我们不需要知道最优解到底是什么，我们只需要求出最优解是多少即可，所以对构造过程可以不进行跟踪。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,10,现在，写出一个递归算法计算通过工厂的最快路线是一件很简单的事情了。只需基于以下几个公式即可：,f*=min(f1n+x1,f2n+x2),fi1=,ei,+ai,1;,fij,=min(fij-1+,ai,j,fij-1+ti,j-1+a2,j),现在我们来看这种算法的时间复杂度，发现它有一个问题,:,它的执行时间是关于,n,的指数形式即,O,（,2n,），这是一个时间复杂度很高的算法。我们来考虑是否能进一步提高它的效率。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,11,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,12,现在考虑这样一种方式,FASTEST-,WAY(a,t,e,x,n),f11=e1+a1,1,f21=e2+a2,1,/,这两行计算,f11,和,f21,的值,For j=2 to n,/,这个循环用来计算,fij,的值,do if f1j-1+a1,j=f2j-1+t2,j-1+a1,j,then f1j=f1j-1+a1,j,else f1j=f2j-1+t2,j-1+a2,j,if f2j-1+a2,j=f1j-1+t1,j-1+a2,j,then f2j=f2j-1+a2,j,if f1n+x1=0;-i),/,从最下层开始，计算每个,x,，,y,位,/,置的元素到 最后一行的最小值,for(j=0;j=i;+j),/,计算每一行的每一个数字,tmp,=,soui,+1j;,if(,soui,+1j+1,tmp,),/*j,在变化，,j,每循环完次都得到一个这一行到最底行最小的位置，同时也记录了每个位置到最底行的值；这里的,if,是在找每个位置的下两步路线中较小的一个,*/,tmp,=,soui,+1j+1;,souij,+=,tmp,;,printf,(%,dn,sou00);,例题二：花束摆放,问题描述,现在有,F,束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架子上，并从,1,至,V,按从左到右顺序编号，,V,是花瓶的数目,(,FV),。花束可以移动，并且每束花用,1,至,F,的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果,ij,，花束,i,必须放在花束,j,左边的花瓶中。每个花瓶只能放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,36,每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以一美学值,(,一个整数,),来表示，空置花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最大美学值的一种摆放方式。,2,解题思路,状态表示法一：,设,A(i,j,),表示第,i,种花束摆在第,j,个花瓶中获得的美学值。,S(i,k,),表示第,i,种花束摆在第,k,个花瓶中时,(,这里,ki,),，前,i,种花束能够获得的最大美学值,(,之和,),。这样，原问题的最优值可以通过计算,maxS(F,k),FkV,获得。,下面要分析一下这种状态表示法描述问题的方式是否具备了用动态规划求解的基本要素。,最优子结构性质：对满足,FkV,的,k,，设,T(F,k,),是达到最优值,S(F,k,),的一种最佳摆放方式，其中，第,F-1,种花束摆在第,j,个花瓶中,(j1,每走一步，计算出了所有,i,的花束摆放在所有可能的位置之后的所有值。最后，递推出了,s(F,*),的值取最大既得到结果。,S(1,k)=A(1,k),第,i-1,个花摆在那里之后，下一步怎么摆，只跟现在花在哪里有关，而与前面的摆放顺序无关，无后效性。,大家用心想一下，问题其实还是像装配线一样，被分解成了有限个分支的最大值问题。,切记，使用,DP,的时候，眼光不要一直盯着最后的最优，一步一步看，只要你现在最优，并且无后效性，就可以,DP,下去。,在计算,S(i,k-1),时，已经计算出了,S(i-1,j),，,i-1jk-2,及其,maxS(i-1,j),i-1jk-2,。因此，计算,S(i,k,),时，只要将,S(i-1,k-1),与,max S(i-1,j),i-1jk-2,进行比较即可求得,即子问题重叠性质。这样做可以大大减少计算量。即不用每次都去全部比较，求最大值。,事实上，还可以有更直接的方法。,状态表示法二：,设,Si,k,表示第,i,种花束摆在第,k,个之前,(,包括第,k,个,),的任意某个花瓶中，前,i,种花束能够获得的最大美学值,(,之和,),。这样，原问题的最优值即为,SF,V,。这比前一个表示法更直接。,容易验证，计算,SF,V,的问题具有最优子结构性质。,其递归方程为：,Si,k,=max,Si-1,k-1+A(i,k),，,Si,k-1,，,(i1,，,ki);,/,很精妙，注意理解,初始条件为：,S1,1=A1,1;,S1,k=maxA(1,k),S1,k-1,，,(k1);,Si,i,=Si-1,i-1+A(i,i),，,(i1),算法设计,(,状态表示法二,),算法的过程如下：,s00=a00;out00=true;,for(j=1;j a0j?s0j-1:a0j;,out0j=(s0j!=s0j-1);,for(i=1;i?=,si,-1j-1+,aij,;,outij,=(,sij,!=,sij,-1);,sij,=,si,-1j-1+,aij,;,outij,=true;,if(i?=,sij,-1;outij,=(,sij,!=,sij,-1);,例题三：最大数字子串,NKOJ 1760,最大数字子串,:,问题描述：输入,n(1=n0,，如果后边是正数的话，完全可以加上这,3,个数（比如后边的,5,）,-1 2 8 5 10,？,相同处理：,-1 2 8 5 10 3 17 12,？,后面是,-15,，加上,12,（前面的子串能形成的最大和）也小于,0,，所以此处应该断开了！记录,-15,！,最后,-1 2 8 5 10 3,17,12-15 1 9 5 14,！,还有一点，如果输入全为非正数的话，那么最大子串就是最大的那个数了！,伪代码：,输入数组,ai,用数组,si,记录当前最大子串和,num,记录最大值。,for(i=0;in;i+),输入,ai;,s0=a0;,num,记录当前最大的数；,if(num=0),最大就为,num!,for(i=1;in;i+),if(si-1 0|(si-1+ai)=0)si=ai;,elsesi=si-1+ai;,num=(num si)?si:num;,/*,条件运算符 （,num,bi,true,则,bi,false,则,num,）,*/,例题四：积木游戏,LRJ,的书，,P119,。,这道题和我们程序设计大赛的时候的第四题（是不是第四？记不清了。）猩猩吃香蕉那题有异曲同工之妙。大家明白这题之后可以回忆一下我们的比赛。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,50,例题五：,Subsequence,给定一个数串和一个数,S,，在数串中找出大于等于,S,的一个连续子列！且该子列是满足上述条件的最短子列！,数串数字个数,N,：,10N100000,每个数小于,10000,。,比如：,10 15,5 1 3,5 10,7 4 9 2 8,最短为,2,；,5 11,1 2,3 4 5,最短为,3,。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,51,该题简单分析,：,题意知所有数全为正数,A sequence of N positive integers(10 N 100 000),，每新增一个数，若前面的数不足,S,加上此数，然后与,S,比较！,小于,S,可不管！,大于,S,：假设此时新增项,ai,设当前和为,sumi,用另一数组记录当前长度位置长度,lengthi,。那么现在在构成,sumi,的数的最前端,i-lengthi+1,处，有可能出现多余的项，哪怕删除它们也满足剩下的数的和,sumi,(,长度已更改为新的,lengthi,!),逐项除之即可！,lengthi,记录的是到达每个位置的时候，这个串现在有多长。,寻找最短子列：,Length,全为,0,没有最短子列,!,否则为大于,0,的最小值。,if(b1n-1=0),num=0;,else,num=n;,for(i=0;i0),num=(b1inum)?b1i:num;,例题六：炮兵阵地,POJ 1185,经典的,DP,问题,题意描述：,司令部的将军们打算在,N*M,的网格地图上部署他们的炮兵部队。一个,N*M,的地图由,N,行,M,列组成，地图的每一格可能是山地（用,H,表示），也可能是平原（用,P,表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,55,如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响,。,现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队,。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,56,Input,第一行包含两个由空格分割开的正整数，分别表示,N,和,M,；接下来的,N,行，每一行含有连续的,M,个字符,(P,或者,H),，中间没有空格。按顺序表示地图中每一行的数据。,N=100,；,M=10,。,Output,仅一行，包含一个整数,K,，表示最多能摆放的炮兵部队的数量。,Sample Input,5 4 PHPP PPHH PPPP PHPP PHHP Sample Output,6,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,57,这道题给大家留做思考题，大家可以先考虑一下，这道题的状态方程该怎么描述，试着,A,一下，但是这个题直接,DP,是,A,不过的，因为不论是时间还是空间都会超，这道题还有一个关键点，就是状态压缩，今天我们已经讲了很多内容了，所以状态压缩的,DP,今天就不讲了，我会在下次的,动态规划,提高篇,中详细讲解这道题。,2009-8-12,成都大学ACM,暑期集训,DP,篇,李明金,58,OK,，今天的课程和题目到这里就完成了，今天的内容很多，但是，还远远达不到对,DP,的哪怕沧海一粟般的描述，而且，,DP,是,ACM,中的重中之重，所以大家下课之后，一定回去将概念和例题多读多看，对概念要理解并掌握，对例题要能熟练的一眼就写出状态方程。,最后，留下几道练习题，大家可以在看熟了课件并掌握了例题之后来试试身手。,地址是：,,D E,（三角形演变题）,H,四道题，题目不多，是江苏省赛的回放中的几道题，大家试下身手。,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,59,谢谢,2009-8-12,成都大学,ACM,暑期集训,DP,篇,李明金,60,