动态规划及其应用ppt课件

.,动态规划及其应用,赖国堃福建师大附中,.,基本概念,动态规划问题的满足两个基本性质一、最优子结构问题可以表示为一些子问题，然后通过求解子问题的最优答案，得到问题答案。二、无后效性当前决策不会影响到之后的决策。,.,动态规划的3个基本要素,状态转移边界这3个一般是做动态规划时要先思考清楚的问题。,.,例题,例1、数字三角形（图2）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1三角形行数100；三角形中的数字为整数0，1，99；输入数据：由INPUT.TXT文件中首先读到的是三角形的行数。在例子中INPUT.TXT表示如下：5738810274445265输出数据：把最大总和（整数）写入OUTPUT.TXT文件。上例为：30,.,分析,只要对该题稍加分析，就可以得出一个结论：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n,则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺序求出第一阶段、第二阶段，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。,.,状态：fI,j表示，走到第i行第j列最大得分转移：fI,j=fi-1,j-1+cI,j(j1)=fI-1,j+cI,j(jListi,j.Tot)ThenListi,j.Tot:=Listi-1,j-1.Tot+Listi,j.Val;若从i-1,j-1选择右斜线向下会使1,1至i,j的数字和最大,则决策该步If(ji)And(Listi-1,j.Tot+Listi,j.ValListi,j.Tot)ThenListi,j.Tot:=Listi-1,j.Tot+Listi,j.Val若从i-1,j选择左斜线向下会使1,1至i,j的数字和最大,则决策该步End;for,.,例题,有一个体积为V背包，现在有n个物品，他们格子有自己的体积vi，和各自的价值wi。现在需要选出一些物品装进背包，你的任务是使装进物品的价值最大。,.,状态：fI,j(i表示处理第几个物品，j表示已用了多大空间)转移：fI,j=max(fi-1,j-vi+ci,fi-1,j)边界：f0,0=0;,.,fori:=1tondoforj:=1tomdobeginifj=vithenfi,j:=max(fi-1,j-vi+ci,fi-1,j)elsefi,j:=fi-1,j;end;,.,例题,【问题描述】假设以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果IJ，则花束I必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。,.,每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时会产生不同的美学效果，并以美学值(一个整数)来表示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示。比如杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中则显得很难看。,.,为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1F100，FV100，50AIJ50，其中AII是花束I摆放在花瓶J中的美学值。输入整数F，V和矩阵(AIJ)，输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。,.,【输入文件】第一行包含两个数：F，V。随后的F行中，每行包含V个整数，Aij即为输入文件中第（i+1）行中的第j个数【输出文件】包含两行:第一行是程序所产生摆放方式的美学值。第二行必须用F个数表示摆放方式，即该行的第K个数表示花束K所在的花瓶的编号。【输入样例】3572352416521-41023-215-4-2020【输出样例】53245,.,方法1,既然要拿花束一个一个的放，我们就以花束划分阶段。在这里，阶段变量k表示的就是要布置的花束数目（前k束花），状态变量sk表示第k束花所在的花瓶。而对于每一个状态sk，决策就是第k-1束花应该放在哪个花瓶，用uk表示。最优指标函数fk(sk)表示前k束花，其中第k束插在第sk个花瓶中，所能取得的最大美学值。,.,规划方程为：（其中A(i,j)是花束i插在花瓶j中的美学值）fI,j=max(fi-1,u+aI,j)(i=uj),.,方法2,以花瓶的数目来划分阶段。在这里阶段变量k表示的是要占用的花瓶数目（前k个花瓶），状态变量sk表示前k个花瓶中放了多少花。而对于任意一个状态sk，决策就是第sk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk(sk)表示前k个花瓶中插了sk束花，所能取得的最大美学值。规划方程为：fI,j=max(fi-1,j,fi-1,j-1+aj,i),.,区间类动态规划,（1）石子合并【问题描述】在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。【输入文件】包含两行，第1行是正整数n（1=n=100），表示有n堆石子。第2行有n个数，分别表示每堆石子的个数。【输出文件】输出两行。第1行中的数是最小得分；第2行中的数是最大得分。【输入样例】44495【输出样例】4354,.,分析看到本题，容易想到使用贪心法，即每次选取相邻最大或最小的两堆石子合并。然而这样做对不对呢？看一个例子。6346542如果使用贪心法求最小得分，应该是如下的合并步骤：第一次合并3465422,3合并得分是第二次合并546545,4合并得分是9第三次合并96545,4合并得分是9第四次合并9699,6合并得分是15第五次合并15915,9合并得分是24总得分599152462但是如果采用如下合并方法，却可以得到比上面得分更少的方法：第一次合并3465423,4合并得分是7第二次合并765427,6合并得分是13第三次合并135424,2合并得分是6第四次合并13565,6合并得分是11第五次合并131113,11合并得分是24总得分7136112461显然，贪心法是错误的。为什么？显然，贪心只能导致局部的最优，而局部最优并不导致全局最优。,.,具体来说我们应该定义一个数组si,j用来表示合并方法，i表示从编号为第i堆的石头开始合并，j表示从i开始数j堆进行合并，si,j为合并的最优得分。则动规方程为：SI,j=minsI,k+si+k,j-k+sumI,j1=k=j-12=jnthent(i+k)modnelseti+k最后一个连第一个的情况处理si,j最优si,k+st,j-k+sum1,3sumi,j表示从i开始数j个数的和end;,.,在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号表示两颗珠子的聚合操作，(jk)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(41)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为(41)2)3）=10*2*3+10*3*5+10*5*10=710。,.,【输入文件】输入文件energy.in的第一行是一个正整数N（4N100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1iN），当i时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。【输出文件】输出文件energy.out只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。【输入样例】423510【输出样例】710,.,算法分析,如果要求一个链的最优合并方式,可以把这个链从中间断开,枚举断开处,分别求出2段的最优合并的值,再将这两端合并,而这条链断开后的2段的最优合并方式也可以用同样的方式计算,因此,本题具有最优子结构性质,可以用动态规划求解但本题中并不是一个链而是一个环,但这并不影响最优子结构性质,可以做一条链,长度是环的2倍,其中前半段与后半段一样,都为环的顺序(可任意确定),那么,从中间任取长度为n的一段,就实现了环的性质首尾相接,.,设fk,j为从珠子k到珠子j的最优合并,那么枚举断开点p,则fk,j的最优值为fk,p的最优值和fp+1,j的最优值的和再加珠子k,p和p+1,j合并的值vk(k的头标记)*vp+1(p的尾标记=p+1的头标记)*vj+1(即j的尾标记)动规方程为:fk,j=maxfk,p+fp+1,j+vk*vp+1*vj+1(kj2*n且k=pj),.,ford=1ton/从小到大枚举链的长度fork=1to2*ndo/枚举链的起点beginj=k+d-1;/计算链的终点if(j=2*n)/若在最大值范围内forp=ktoj-1/枚举断开点begin根据方程更新fk,j的值;end;end;,.,例题,1、加分二叉树（noip2003）【问题描述】设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分subtree的右子树的加分subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树tree。要求输出；（1）tree的最高加分（2）tree的前序遍历,.,【输入格式】第1行：一个整数n（n30），为节点个数。第2行：n个用空格隔开的整数，为每个节点的分数（分数100）。【输出格式】第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。第2行：n个用空格隔开的整数，为该树的前序遍历。【输入样例】5571210【输出样例】14531245,.,.,如果整棵树的权值最大，必然有左子树的权值最大，右子树的权值也最大，符合最优性原理本题适合用动态规划来解。如果用数组fi,j表示从节点i到节点j所组成的二叉树的最大加分，枚举根节点，则动态方程可以表示如下：fi,j=maxi0thenbegindfs(i+1,r);ifs0thens:=s*fi+1,relses:=fi+1,r;end;inc(s,ai);ifsfl,rthenbeginfl,r:=s;dl,r:=i;end;end;end;,.,树形动态规划,顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：1、根叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题，所以不在今天讨论的范围之内。2、叶根：既把根的子节点传递有用的信息给根，完成后根得出最优解的过程。这类的习题比较的多，下面就介绍一些这类题目和它们的一般解法。（树的后序遍历求解）,.,2、Ural1018二叉苹果树【问题描述】有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树25/34/1现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。输入格式第1行2个数，N和Q(1=Q=N,1N=100)。N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。输出格式一个数，最多能留住的苹果的数量。,.,样例输入52131141023203520样例输出21,.,分析：因为题目一给出就是纯二叉的树结构，如果要保留住最多苹果数量，必然是左子树保留尽量多，右子树也保留尽量多，满足最优性原理,我们定义状态,fi,j表示以i为根的子树(还包括i与i的父亲这条边)内,保存j条边最多可以有多少苹果,显然fi,j=max(flefti,k+frighti,j-k-1)+applei,fatheri;（0=k=j-1）边界：f0,i=0;fi,0=0;问题的解：f1,q+1;虚拟了一条边，也就相当于多添加了一个节点1的父亲节点，这条边为1和它父亲节点的,.,proceduretree_dp(t,k:integer);vari,ls,rs:integer;beginifft,k0thenexit;if(t=0)or(k=0)thenbeginft,k:=0;exit;end;ft,k:=0;fori:=0tok-1dobegintree_dp(treet.lc,i);/左子树tree_dp(treet.rc,k-i-1);/右子树ls:=ftreet.lc,i;/记录左子树的值rs:=ftreet.rc,k-i-1;/记录右子树的值ifft,kls+rsthenft,k:=ls+rs;/比较end;ft,k:=ft,k+treet.s;/保存最优值end;,.,例题,问题描述在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？输入：第一行有两个整数N,M用空格隔开。(1=N=200,1=M=150)接下来的N行,第I+1行包含两个整数ki和si,ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1=ki=N,1jthenj:=i;end;bx,y:=j;end;,.,beginreadln(s);assign(input,s);reset(input);readln(n,m);fillchar(f,sizeof(f),0);fori:=0tondobeginai.l:=-1;ai.r:=-1;ai.k:=-1;end;建树fori:=1tondobeginreadln(k,l);ai.k:=l;iffk=0thenak.l:=ielseafk.r:=i;fk:=i;end;,.,边界fori:=-1tondoforj:=-1tomdoif(i=-1)or(j=0)thenbi,j:=0elsebi,j:=-1;记忆化实现动规treedp(a0.l,m);输出writeln(ba0.l,m);end.时间复杂度最大为O(n3)思考:若本题加上选那些课程可得到这个最大学分,怎样修改程序？,.,4、河流(IOI2005)一颗有N+1个结点的树，树中的每个结点可能会生产出一些产品。这些产品要么就地加工（要有加工厂才行），要么运送到它的父亲结点那儿去。现在在整棵树的根结点处已经有了一个产品加工厂，而且所有的产品最终必须在某个加工厂加工才行。由于运费昂贵，不可能将所有的产品都运送到根节点处加工。现在决定在树中的某些结点新增总共K个加工厂，现在要你选择这K个加工厂的厂址。假设结点i会生产出Wi吨产品，它的父结点是Pi。而它到它的父结点的路径的长度是Ui。运费的计算是每运送1顿的货物，每单位长度收取1的费用。根节点的编号为0。,.,例如下图，0节点是根节点，如果要新增两个工厂，最佳方案是建在2、3两个节点上，这样总的费用为：1*1（1号）+1*3（4号）=4,.,分析：由于题目中给出的树是多叉树，不便于进行动态规划。我们先利用儿子兄弟表示法，将多叉树转化为二叉树进行了相关的转化之后，设f(i,j,k)表示在新树中，以i结点为根的子树中，分配k个加工厂。并且离i结点最近的加工厂在j结点的情况下。i结点及其子树内的所有产品，加工所需要的费用。转移方程很容易就可以写出来：总时间复杂度为O(N2K2)。,.,状态压缩动态规划,有一些问题却被认为很可能不存在有效的(多项式级的)算法，这里以对几个例题的剖析，简述状态压缩思想及其应用。,.,预备知识,.,引例,在n*n(n20)的方格棋盘上放置n个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。,.,分析,其实本题是一个简单的组合数学问题，因为每行有且仅有一个车，所以我们只要来考虑每行上列的问题，显然每列只能出现一次，这题答案就是n的一个全排列，为P(n,n)=n!当然这题还有状态压缩的解法。,.,分析,我们仍然一行一行放置。取棋子的放置情况作为状态，某一列如果已经放置棋子则为1，否则为0。这样，一个状态就可以用一个最多20位的二进制数表示。例如n=5,第1、3、4列已经放置，则这个状态可以表示为01101(从右到左)。设fs为达到状态s的方案数，则可以尝试建立f的递推关系。,.,前两行在第3、4列放置了棋子(不考虑顺序，下同)，第三行在第1列放置；前两行在第1、4列放置了棋子，第三行在第3列放置；前两行在第1、3列放置了棋子，第三行在第4列放置。,.,.,这三种情况互不相交，且只可能有这三种情况，根据加法原理，fs应该等于这三种情况的和。根据上面的讨论思路推广之，得到引例的解决办法：其中s的右起第i+1位为1(其实就是在枚举s的二进制表示中的1),.,状态压缩具有良好的拓展性。在n*n(n20)的方格棋盘上放置n个车，某些格子不能放，求使它们不能互相攻击的方案总数。我们只需要在原题的程序中枚举添加1的位置的时候进行判断就行。,.,programp1;constmax=1shl20;varn,i,t,c,j,tmp,r:longint;f,a:array0.maxofint64;beginassign(input,p1.in);areset(input);readln(n);fillchar(f,sizeof(f),0);fori:=1tondo/读入及预处理beginai:=0;forj:=1tondo/如果第i行的某位为0,表示这位不能放置beginread(c);ai:=aishl1;ifc=1thenai:=ai+1;end;end;,.,f0:=1;fori:=1to(1shln)-1dobegint:=i;r:=0;whilet0do/计算状态i中1的个数，即可得到其为第几行begininc(r);t:=t-(tand-t);end;tmp:=iandar;t:=tmp;whilet0do/枚举状态tmp二进制表示中的1beginfi:=fi+fixor(tand-t);t:=t-(tand-t);end;end;writeln(f(1shln)-1);end.,.,当然这个问题也可以用容斥原理解决，但这个不是今天的主题，有兴趣的同学可以自己思考。,.,例题,有一个n*m的棋盘(n、m80