动态归划教程.doc

目录1、引言2、动态规划的基本原理2.1多阶段决策过程最优化问题2.2动态规划的基本概念2.3使用动态规划解题的必要条件2.4动态规划的一般步骤3、动态规划解题的实际应用3.1数字三角形3.2导弹序列3.3最长公共子序列3.4排队买票3.5背包问题系列3.6乘积最大3.7石子归并 官方教程 我的讲稿1、引言动态规划算法十分重要，其实质是分支思想和解决冗余，因此它与分支法和贪心法类似，他们都是将问题的实例分解为更小、相似的子问题，但是动态规划又有自己的特点。贪心法的当前选择可能要以来于已经做出的选择，但不依赖还未做出的选择和子问题，因此他的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。在用分支法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式数量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是：用一个表记录所有已解决的自问题的答案，不管该问题以后是否被用到，只要它被计算过，就将结果填入表中。所以动态规划思想实质是记忆化搜索的思想。动态规划的思想是对于贪心法和分支法的一种折衷，它解决的问题往往不具有贪心算法的实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题有不同特色的表示方法。2、动态规划的基本原理2.1多阶段决策过程最优化问题在现实生活中，有一类活动的过程，由于他的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要做出决策，从而使整个过程达到最佳的活动效果。因此各个阶段决策的选取不是任何确定的，它以来于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把问题看作是一个前后关联且具有链装结构的多阶段过程，被称为多阶段决策问题，这种问题就称为多阶段决策问题。如图所示:决策1阶段n状态1决策1决策n状态0状态2阶段1阶段2状态2例 最短路径问题：如图所示的是一个带权有向的多段图，要求从A到D的最短路径的长度(下面简称最短距离)。C1C3D1AB1B3B2D2EC22511214106104131112396581052图6.1如果用穷举法，则从A到E一共有332=18条不同的路径，逐个计算每条路径的长度，总共需要进行418=72次加法计算；对18条路径的长度做两两比较，找出其中最短的一条，总共要进行181=17次比较。如果从A到C的站点有k个，则总共有3k-12条路径， 用穷举法求最短路径总共要进行(k+1)3k-12次加法，3k-12-1次比较。当k的值增加时，需要进行的加法和比较的次数将迅速增加。例如当k=10时，加法次数为433026次，比较39365次。以上这求从A到E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子问题，即分别从B1、B2、B3到E的最短路径问题。记从Bi (i=1, 2, 3) 到E的最短路径为S(Bi)，则从A到E的最短距离S(A)可以表示为：同样，计算S(B1)又可以归结为性质完全相同，但规模更小的问题，即分别求C1，C2，C3到E的最短路径问题S(Ci) (i=1, 2, 3)，而求S(Ci)又可以归结为求S(D1)和S(D2)这两个子问题。从图1.1.1可以看出，在这个问题中，S(D1)和S(D2)是以知的，它们分别是：S(D1)=5，S(D2)=2因而，可以从这两个值开始，逆向递归计算S(A)的值。计算过程如下：即S(C1)=8且如果到达C1，则下一站应到达D1；S(C2)=7且如果到达C2，则下一站应到达D2；S(C3)=12且如果到达C3， 则下一站应到达D2；由此，可以计算S(Bi)：即S(B1)=20且如果到达B1，则下一站应到达C1；S(B2)=14且如果到达B2，则下一站应到达C1；S(B3)=19且如果到达B3，则下一站应到达C2；由此，可以计算S(A)：最后，可以得到：从A到E的最短路径为A B2 C1 D1 E以上计算过程及结果，可用图6.2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。820052712141919C1C3D1AB1B3B2D2EC22511214106104131112396581052图6.2以上过程，仅用了18次加法，11次比较，计算效率远高于穷举法。2.2动态规划的基本概念由例可以看出，动态规划问题具有以下基本特征：1、问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。2、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。3、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“不变嵌入”。为了将以上特征形式化，我们提出以下动态规划的基本概念。阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。状态Sk：能确定地表示决策过程决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。状态变量xk：表示每一状态可以取不同值的变量。决策（Decision）dk：从某一状态向下一状态过度时所做的选择。决策是所在状态的函数，记为dk(xk)。决策允许集合Dk(xk)：在状态xk下，允许采取决策的全体。状态转移方程xk+1=T(xk,dk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。阶段指标函数vk(xk,dk)：从状态xk出发，选择决策dk所产生的第k阶段指标。过程指标函数V(xk,dk,dk+1,dn)：从状态xk出发，选择决策dk,dk+1,dn所产生的过程指标。动态规划要求过程指标具有可分离性，即Vk,n(xk, dk,dk+1,dn)=vk(xk,dk)+Vk+1(xk+1,dk+1,dn)称指标具有可加性，或Vk,n(xk, dk,dk+1,dn)=vk(xk,dk)Vk+1(xk+1,dk+1,dn)称指标具有可乘性。最优指标函数fk(xk)：从状态xk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即对于可加性指标函数，上式可以写为对于可乘性指标函数，上式可以写为以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(xn)的值。C1阶段5阶段4阶段3阶段2阶段1图6.32510856931211134106101412152C2ED2B2B3B1AD1C3利用以上基本概念，重新求解例将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)=B3C1, B3C2, B3C3最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。第四阶段的递推方程为：从f5(x5)到f4(x4)的递推过程用下表表示： x4D4(x4)x5v4(x4,d4)v4(x4,d4)+f5(x5)f4(x4)最优决策d4*D1D1EE55+0=5*5D1ED2D2EE22+0=2*2D2E其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：f4(x4) 的表达式x4f4(x4)最优决策d4*D15D1ED22D2E第三阶段的递推方程为：从f4(x4)到f3(x3)的递推过程用表格表示如下：x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)最优决策d3*C1C1D1C1D2D1D2 3 9 3+5=8* 9+2=118C1D1C2C2D1C2D2D1D2 6 5 6+5=11 5+2=7*7C2D2C3C3D1C3D2D1D2 810 8+5=1310+2=12*12C3D2由此得到f3(x3)的表达式：x3f3(x3)最优决策d3*C18C1D1C27C2D2C312C3D2第二阶段的递推方程为：从f3(x3)到f2(x2)的递推过程用表格表示如下：x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)最优决策d2*B1B1C1B1C2B1C3C1C2C312141012+8=20*14+7=2110+12=2220B1C1B2B2C1B2C2B2C3C1C2C3 610 46+8=14*10+7=174+12=1614B2C1B3B3C1B3C2B3C3C1C2C313121113+8=2112+7=19*11+12=2319B3C2由此得到f2(x2)的表达式：x2f2(x2)最优决策d2*B120B1C1B214B2C1B319B3C2第一阶段的递推方程为：从f2(x2)到f1(x1)的递推过程用表格表示如下：x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)最优决策d1*A A B1A B2AB3B1B2B32 512+20=225+14=19*1+19=2019A B2由此得到f1(x1)的表达式：x1f1(x1)最优决策d1*A19A B2从表达式f1(x1)可以看出，从A到E的最短路径长度为19。由f1(x1)向f4(x4)回朔，得到最短路径为：A B2 C1 D1 E2.3使用动态规划解题的必要条件1 最优化原理 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状 图2态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。 如图2中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径J是B到C的最优路径，则A到C的路线取I和J比I和J更优，这与原名题矛盾。从而证明J必是B到C的最优路径。最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。2 无后效性 “过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结”。这条特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策略任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性的内涵。由上可知，最优化原理，无后效性，是动态规划必须符合的两个条件。2.4动态规划的一般步骤从阶段1出发，一次枚举各个阶段的所有状态，将每个子问题代入状态转移方程计算一次，充分利用重叠子问题，由于这种方式无须递归代价因此其效率好于自上而下求解方式。按照阶段、状态和决策的层次关系，我们给出程序流程的一般形式： 所有状态u的最小费用初始化： 0, u=u0;Iu= , uu0.For k:=阶段最小值 to 阶段最大值 do 顺推每一个阶段For u:=状态最小值班to 状态最大值 do 枚举阶段k 的每一个状态 For x:=决策最小值班 to 决策最大值 do 枚举阶段k中状态u可选择的每一种决策Begin Iuk:=minik-1+Luk-1,xk-1|uk-1通过决策xk-1可达ukEnd;for 需要注意，上述陈规流程仅是提供了自下而上方式解题的确一种思路，并不是说所有的自下而上方式解题的程序流程都如此。我们必须根据实际问题和解题需要出发，具体问题具体分析，制定行之有效的策略。3、动态规划在解题中的应用例1 数字三角形（IOI94）问题描述 如下所示为一个数字三角形 73 88 1 02 7 4 44 5 2 6 5请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字总和最大。1. 每一步可沿直线向下或右斜线向下走；2. 1三角形行数maxsum(i+1,j+1) then maxsum:=maxsum(i+1,j)+ai,j else maxsum:=maxsum(i+1,j+1)+ai,jend;begin readln(line); for i:=1 to line do 产生数据 begin for j:=1 to i do begin ai,j:=random(99)+1; write(ai,j:3) end; writeln end; writeln; writeln(Maxsum=,maxsum(1,1); max1,1:=a1,1; for i:=2 to line do begin maxi,1:=maxi-1,1+ai-1,1; for j:=2 to i-1 do if ai,j+maxi-1,j=ai,j+maxi-1,j-1 then maxi,j:=ai,j+maxi-1,j else maxi,j:=ai,j+maxi-1,j-1; maxi,i:=maxi-1,i-1+ai,i end; t:=0; for i:=1 to line do if t1,fi-1,j|I1+aij,边界条件：F1,1=a1,1 answer=Fnm例2 拦截导弹某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUT OUTPUT389 207 155 300 299 170 158 65 6（最多能拦截的导弹数） 2（要拦截所有导弹最少要配备的系统数）问题分析 第一部分是要求输入数据串中的一个最长不上升序列的长度，可使用递推的方法，具体做法是从序列的第一个元素开始，依次求出以第i个元素为最后一个元素时的最长不上升序列的长度len(i)，递推公式为len(1)=1，len(i)=max(len(j)+1)，其中i1，j=1,2,i-1，且j同时要满足条件：序列中第j个元素大于等于第i个元素。 第二部分比较有意思。由于它紧接着第一问，所以很容易受前面的影响，采取多次求最长不上升序列的办法，然后得出总次数，其实这是不对的。要举反例并不难，比如长为7的高度序列“7 5 4 1 6 3 2”， 最长不上升序列为“7 5 4 3 2”，用多次求最长不上升序列的结果为3套系统；但其实只要2套，分别击落“7 5 4 1”与“6 3 2”。那么，正确的做法又是什么呢？我们的目标是用最少的系统击落所有导弹，至于系统之间怎么分配导弹数目则无关紧要；上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势，忽视了最优解中各个系统拦截数较为平均的情况，本质上是一种贪心算法。如果从每套系统拦截的导弹方面来想行不通的话，我们就应该换一个思路，从拦截某个导弹所选的系统入手。题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导弹高度，所以，当已有的系统均无法拦截该导弹时，就不得不启用新系统。如果已有系统中有一个能拦截该导弹，我们是应该继续使用它，还是另起炉灶呢？事实是：无论用哪套系统，只要拦截了这枚导弹，那么系统的瞄准高度就等于导弹高度，这一点对旧的或新的系统都适用。而新系统能拦截的导弹高度最高，即新系统的性能优于任意一套已使用的系统。既然如此，我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹，究竟选哪一个呢？当前瞄准高度较高的系统的“潜力”较大，而瞄准高度较低的系统则不同，它能打下的导弹别的系统也能打下，它够不到的导弹却未必是别的系统所够不到的。所以，当有多个系统供选择时，要选瞄准高度最低的使用，当然瞄准高度同时也要大于等于来犯导弹高度。解题时，用一个数组记下已有系统的当前瞄准高度，数据个数就是系统数目。程序清单const max=1000;var i,j,current,maxlong,minheight,select,tail,total:longint; height,longest,sys:array 1.max of longint; line:string;begin write(Input test data:); readln(line); i:=1; while i=length(line) do begin while (i=length(line) and (linei= ) do i:=i+1; current:=0; while (i=length(line) and (linei ) do begin current:=current*10+ord(linei)-ord(0); i:=i+1 end; total:=total+1; heighttotal:=current end; longest1:=1; for i:=2 to total do begin maxlong:=1; for j:=1 to i-1 do begin if heightimaxlong then maxlong:=longestj+1; longesti:=maxlong end; end; maxlong:=longest1; for i:=2 to total do if longestimaxlong then maxlong:=longesti; writeln(maxlong); sys1:=height1; tail:=1; for i:=2 to total do begin minheight:=maxint; for j:=1 to tail do if sysjheighti then if sysjminheight then begin minheight:=sysj; select:=j end; if minheight=maxint then begin tail:=tail+1; systail:=heighti end else sysselect:=heighti end; writeln(tail)end. 思考：最长递减子序列（全国青少年信息学联赛培训教材（复赛篇）第6章例2）给定数列a1,a2,.an,求最长递减子序列输入数据：n和n个数据（n=100）输出数据：最长递减子序列拓展：合唱队形N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK，则他们的身高满足存在i（1=i=K）使得TiT2.Ti-1Ti+1.TK。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。输入的第一行是一个整数N(2=N=100)，表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130=Ti=230)是第i位同学的身高(厘米)。输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。样例输入8186 186 150 200 160 130 197 220样例输出4数据规模 对于50的数据，保证有n=20； 对于全部的数据，保证有n=100。动态规划。最基本的想法是：枚举中间最高的一个人，接着对它的左边求最长上升序列（注意序列中最高的同学不应高过基准），对右边求最长下降序列（同样的，序列中最高的同学不应高过基准）。时间复杂度为O(n3)，算法实现起来也很简单。接着对这个算法进行分析，我们不难发现，假如还是基于枚举一个同学的话，设Incsqi表示了1 - i的最长上升序列，Decsqi表示了i - n的最长下降序列，那么，Currenti = Incsqi + Decsqi - 1（两个数组中i被重复计算了）那么，我们只需要先求好最长上升和下降序列，然后枚举中间最高的同学就可以了。求最长上升序列的经典状态转移方程为：opti = maxoptj+1, 其中ijlisti我们对状态转移方程稍微做一些修改：opti = maxopti+1, minj, recj=listirecj = listi很明显可以看出，在opti的寻找j的过程当中，查询序列是单调的，于是可以用二分法，就十分巧妙地在logn的时间内找到指定的j，而问题的总体复杂度为O(nlogn)。这样，这个问题的算法效率就得到了大幅度的提升，即便n是106，也可以轻松应对。例3 最长公共子序列问题描述 一个给定的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定的序列X=,则另一个序列Z=是X的子序列是指存在一个严格递增的下标序列,使得对于所有的j=1,2,.k,有 Xij=Zij例如，序列Z=是序列X=的子序列，相应的递增下标序列为.给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X=和Y=,则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长的公共子序列，因为X和Y没有长度大于4的公共子序列。给定两个序列X=和Y=,要求找出X和Y的一个最长公共子序列。输入：输入文件共有两行，每行为一个大写字母构成的长度不超过200的字符串，表示序列X和Y.输出：输出文件第一行为一个非负数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出文件仅有一行输出一个整数0，否则在输出文件的第二行输出所求得的最长公共子序列（也是用大写字母组成的字符串表示），如符合条件的最长公共子序列不止一个，只需输出其中任意一个样例输入：ABCBDAB BDCABA样例输出：4 BCBA问题分析动态规划算法可以有效地解决此问题。下面我们按照动态规划算法的各个步骤来设计一个解决此问题的有效算法。4. 最长公共子序列的结构解最长公共子序列的问题最容易想到的算法是穷举算法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查的过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列1，2，。m的一个子序列，因此，X共有2m个不同的子序列，从而穷举算法需要指数时间。事实上，最长公共子序列问题也有最优子结构性质，因此我们有如下定理：定理一：LCS的最优子结构性质设序列X=和序列Y=的一个最长公共子序列Z=则： 若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列； 若xmyn,且zkym,则Z是Xm-1和Y的最长公共子序列； 若xmyn，且zkyn,则Z是X和Yn-1的最长公共子序列。其中Xm-1=,Yn-1=,Zk-1=证明见 这个定理告诉我们，两个序列的最长公共子序列包含了两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。5. 子问题重叠性质由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm（=yn）即可求得X和Y的一个最长公共子序列。当xmyn时，必须解两个自问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长的即为X和Y的一个最长公共子序列。由此递归结构容易看出最长公共子序列问题具有自问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个问题都包含一个公共子问题，及计算Xm-1和Yn-1的最长公共子序列。我们来建立子问题的最优值的递归关系。用cI,j记录序列Xi和Yi的最长公共子序列的长度，其中Xi=,Yj=.当I=0或j=0时，空序列时Xi和Yj的最CI,j=0 I，j=0CI-1,j-1+1 当I,j0,且xi=yj时Max（cI,j-1,cI-1,j） 当I，j0且xiyj时长公共子序列，故cI,j=0,其他情况，由定理可建立递归关系如下：6.7.8.9.10. 计算最优值直接利用上式容易写出一个计算cI,j的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有O(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优解能提高算法的效率。 计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c0.m,0.n和b1.m,1.n.其中cI,j存储Xi与Yj的最长公共子序列的长度，bI,j记录指示cI,j的值是由哪一个自问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录在cm,n中，由于每个数组单元的计算耗费O(1)时间，算法LCS_LENGTH耗时O（mn）.4构造最长公共子序列 由算法计算得到的数组b可用于快速构造序列X=x1,x2,xm)和Y=的最长公共公共子序列。首先从bm,n开始，沿着其中的箭头所指的方向在数组b中搜索。分三种情况构造最长公共字串。在本算法中，每一次的递归调用使I或j减一，因此算法的计算时间为O(m+n)。 参考程序 Program p8_2(Input, Output);const maxlen=200;var i,j:longint; c:array0.maxlen,0.maxlen of byte; x,y,z:string;begin assign(input,lcs.in); reset(input); readln(x); readln(y); close(input); fillchar(c,sizeof(c),0); for i:=1 to length(x) do for j:=1 to length(y) do if xi=yj then ci,j:=ci-1,j-1+1 else if ci-1,jci,j-1 then ci,j:=ci-1,j else ci,j:=ci,j-1; z:=; i:=length(x); j:=length(y); assign(output,lcs.out); rewrite(output); writeln(ci,j); while (i0) and (j0) do if xi=yj then begin z:=xi+z;i:=i-1;j:=j-1 end else if ci-1,jci,j-1 then i:=i-1 else j:=j-1; if z then writeln(z); close(output)end.拓展麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。 每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。输入输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。输出输出文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。你可以相信问题一定有解，但解不一定是唯一的。样例FATBOY.INcecqbhvaiaedpibalukcabegviapcihlaaugckadceevfdadaepcialaukdFATBOY.OUTcevapiluk 算法提示：lcsi,j,k=maxlcsi,j-1,k,lcsi,j,k-1,lcsi-1,j,k,lcsi-1,j-1,k-1+1 (ai=bj=ck)必须满足max(i,j,k)=wi then (背包剩余空间可以放下物品 i )r1:=Make(i-1,j-wi)+vi; (第i件物品放入所能得到的价值 )r2:=Make(i-1,j) (第i件物品不放所能得到的价值 ) Make:=maxr1,r2end;这个算法的时间复杂度是O(2n)，我们可以做一些简单的优化。由于本题中的所有物品的重量均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重复计算这些结点，所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重复计算的话，速度就会提高很多。这是简单的以空间换时间。我们发现，由于这些计算过程中会出现重叠的结点，符合动态规划中子问题重叠的性质。同时，可以看出如果通过第N次选择得到的是一个最优解的话，那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。考虑用动态规划的方法来解决，这里的：阶段是：在前N件物品中，选取若干件物品放入背包中；状态是：在前N件物品中，选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值；决策是：第N件物品放或者不放；由此可以写出动态转移方程：我们用fi,j表示在