《动态规划(动态程序设计)课件.ppt》由会员分享，可在线阅读，更多相关《动态规划(动态程序设计)课件.ppt（247页珍藏版）》请在三一办公上搜索。
1、动态规划,上海市控江中学 王建德,讨论的问题,1、动态规划的基本概念2、动态规划的基础题型3、动态规划的综合题型,基本概念,动态程序设计是解决多阶段决策最优化问题的一种思想方法。所谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。,问题的引出： P是出发点，从P到A，求最短路径,思路,令 从P A的最短路径为P(A)；P(A) = minP(B)+2, P(C)+3；,从P B的最短路径为P(B)；P(B) = minP(D)+1, P(E)+2；,从
2、P C的最短路径为P(C); P(C) = minP(E)+5, P(F)+4；,上述递推公式告诉我们，要求P(A)需要先求出阶段5中的P(B)和P(C)；要求 P(B) (或者P(C)），又要先求出阶段4中的 P(D) 和 P(E) (或P(F)和P(E)（倒推）显然，要依照上述递推过程求解，需要倒过来，从P(P)出发，先求出第一阶段的P(O)和P(N)，再求第二阶段的P(K)，P(L)，P(M)；，最后得到P(A)（顺推）。,数据结构将每条路经的长度存在数组中东西方向上的道路长度存在两维数组h43中,规定数组的第一维为行号，第二维为列号。,h43 = 3,2,3,2,1,4,3,4,5,3
3、,1,2;,南北方向上道路长度存至数组v34中，也规定第一维为行号，第二维为列号。,v34 =2, 2, 3, 4,4, 1, 2, 4,1, 2, 2, 3;,求解过程为从(0, 0)到(3, 3)求最短路径问题定义二维数组，P44=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,第一维为行，第二维为列。这时P(O)为P01；P(N)为P10；P(A)为P33，以下为分阶段递推求解过程。,P00 = 0;,阶段1: P01 = P00+h00 = 0+3 = 3; P10 = P00+v00 = 0+2 = 3;,阶段2: P11 = min P01+v01, P10+h10
4、= min3+1, 2+2 = 4 P02 = P01+h10 =3+2=5; P20 = P10+v10 = 2+4 = 6,阶段3: P12 = min P02+v02, P11+h11= min5+3, 4+1 = 5 P03 = P02+h02 =5+3=8 ; P30 = P20+v20 = 6+1=7 P21 = min P11+v11, P20+h20= min4+1, 6+1 = 5,阶段4: P13 = min P03+v03, P12+h12= min8+4, 5+4 = 9 P22 = min P12+v12, P21+h21= min5+2, 5+4 = 7 P31 =
5、 min P21+v21, P30+h30= min5+2, 7+3 = 7,阶段5: P23 = min P13+v13, P22+h22= min9+4,7+5=12 P32 = min P22+v22, P31+h31= min7+2, 7+1 = 8,最后:P33 = min P23+v23, P32+h32 = min/*12+3, 8+2 = 10,综上，数组P的通项表示为Pij=min(pi-1j+vi-1j),(pij-1+hij-1) ) (i, j0)P0j=P0j-1+h0j-1( i=0, j0)Pi0=Pi-10+vi-10( i0, j=0),P数组数据,圆圈内为路
6、口对P点的最小距离,箭头为最佳行走路径。,for j 1 to 4 do /*计算0行上的每点的距离*/ p0j p0j-1+h0j-1; For i 1 to 4 do /*计算0列上的每点的距离*/ pi0 pi-10+vi-10; for i 1 to 4 do for j 1 to 4 do pijmin( ( pi-1j+vi-1j), (pij-1+hij-1) );For i3 downto 0 do /*输出每个路口对P点的最小距离*/ for j 0 to 3 do write(pij:4) writeln;/*for*/,程序,阶段：据空间顺序或时间顺序对问题的求解划分阶段
7、。 状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。 决策：根据题意要求，对每个阶段所做出的某种选择性操作。 状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。 多阶段决策过程：将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。,动态规划的几个要素,“最优性原理”：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。 最优决策序列的子序列，一定是局部最优决策子序列。注意包含有非局部最优的决策子序列，一定不是最优决策
8、序列,例如贪心法。,动态规划的依据“最优性原理”,动态规划的指导思想,在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。 贪心法:产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的，因为有些问题不符合最优性原理。 动态规划:产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列。,2、动态规划的基础题型,1、路径问题2、01背包问题3、求最佳子序列问题4、双重动态规划,路
9、径问题的讨论,问题的一般形式： 1、计算所有路径方案 2、计算一条最佳路径 3、计算两条最佳路径（多进程的最优化决策）一般方法： 按照出发点走出的步数划分阶段，将当前步可达的顶点集定义为状态，当前步如何走定义为决策。注意： 1、可能需要将原题转化为路径问题 2、如果最佳路径问题不满足最优子结构特征特征的话，可以转化为判定性问题求解。,一、计算所有方案,对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态规划方法呢？如果我们可以找出状态转移的关系，并在状态转移方程,中去掉最佳性要求opt（min或max），将扩展子状态的所有行动作为决策，则可以例举出由初始状态至目标状态的所有方案。显然，在
10、计数类问题中使用这种方法要比回溯法等搜索算法简捷许多。,例题 过河卒,如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。,同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制8个点（图中的P1，P2.P8）。卒不能通过对方马的控制点。 棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：CA，同时CB）。现在要求你计算出卒从A 点能够到达B点的路径的条数。输 入：键盘输入B点的坐标(n,m)以及对方马的坐标（X，Y）
11、输 出：屏幕输出一个整数（路径的条数）。,按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（0，0）或（n,m）为控制点，则输出路径数为0。设constmove:array1.8,1.2of integer /* movek，1.2为马沿k方向跳跃一步的水平增量和垂直增量*/ =(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)；var list:array-1.20,-1.20of comp；/*listi,j为卒从(0,0)到(i,j)
12、的路径数*/ can:array0.20,0.20of boolean；/*cani,j为允许卒通行(i,j)的标志*/,1、计算对方马的控制点,设马的初始位置为（x,y）。按照下述方式计算can序列,canx,y false； /* 对方马所在的点为控制点*/for i1 to 8 do /*从（x，y）出发，沿8个方向计算控制点*/ jx+movei,1；/*计算i方向的跳马位置(j，k)*/ ky+movei,2； if (j=0)and(k=0)and(j=n)and(k=m) /*若（j,k）在界内，则为控制点*/ then canj,kfalse；/*for*/if (not ca
13、n0,0)or(not cann,m) /*若卒的起点和终点为控制点，则输出路径数0*/ then writeln(0) else计算和输出卒从（0，0）走到（n,m）点的路径数listn,m ；/*else*/,我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（i,j）(0in，0jm)设为阶段和状态。 首先，将卒的出发点（0，0）的路径数设为1，该位置设为控制点（list0,01;can0,0 fals）。然后从（0，0）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数:若（i，j）为可行点，则走前位置（i-1,j）和（i,j-1）的路径数加起来，即为从（0，0）
14、走到（i，j ）的路径数，即listi,j=listi-1,j+listi,j-1（i，j）非控制点依次类推，最后得出的listn,m即为问题的解。由此得出算法：fillchar(list,sizeof(list),0)； /*路径数序列初始化*/list0,01；can0,0 false； /*卒从（0，0）出发的路径数为1，该位置不再允许卒通行*/for i0 to n do /*按照由上而下、由左而右计算从(0,0)到每个可行点的路径数*/ for j0 to m do if cani,jthen listi,jlisti-1,j+listi,j-1；输出卒从（0，0）走到（n,m）点的
15、路径条数listn,m；,2、计算和输出卒从（0，0）走到（n,m）点的路径条数,计算一条最佳路径,以路径长度划分阶段，从出发点走i步可达的顶点集合为状态。设fi,j为到达阶段i的顶点j的最优解。 枚举第i-1阶段中与状态j相连的状态k,其子问题的最优解 fi-1,k+状态k至状态j的决策代价wk,j即为阶段i的状态j的一种方案。枚举了所有可能方案后即可得出fi,j。,fi-1,k1,Wk1,j,fi-1,k2,Wk2,j,fi-1,kp,Wkp,j,寻宝游戏,分析,在“藏宝图”中寻求一条含len个顶点的路径，使得(1klen)(xk,yk)-ak)2最小。,数据结构,const ex:arr
16、ay1.4of shortint=(0,0,1,-1); ey:array1.4of shortint=(1,-1,0,0);var n,m,len,i,j,k,l,i0,j0:integer; /*n,m为“藏宝图”的规模*/ mp:array1.50,1.50of integer; /*“藏宝图”*/ c0,c1:array1.50,1.50of longint; /*c0I,j为ck-1,I,j; c1I,j为ck,I,j*/ a:array1.150of integer; /*数列*/ ans:longint; /*数列与表格的接近程度*/,输入信息，计算c0的初始值,readln(f
17、,n,m); /*输入“藏宝图”的规模*/for i1 to n do /*输入“藏宝图”*/ for j1 to m do read(f,mpi,j);readln(f,len); /*输入数列的项数len*/for i1 to len do read(f,ai); /*输入数列*/for i1 to n do /*计算初始解*/ for j1 to m do c0i,jsqr(a1-mpi,j);,for k2 to len do /*阶段:路径长度*/ for i1 to n do /*状态:当前位置*/ for j1 to m do c1i,jmaxint; for l1 to 4 d
18、o /*决策:选择最佳移前位置*/ i0i+exl; j0j+eyl; if (i0 in 1.n) and (j0 in 1.m) and (c0i0,j0c1i,j) then c1i,jc0i0,j0 ; /*for*/ c1i,jc1i,j+sqr(mpi,j-ak) ; /*for*/ c0c1 ; /*for*/ansmaxint; /*计算ansminc1I,j*/for i1 to n do for j1 to m do if c1i,jans then ansc1i,j;writeln(,ans)/*输出数列与表格的接近程度*/,Hanoi双塔问题,【问题描述】 给定A,B,
19、C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将 这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求: (1)每次只能移动一个圆盘； (2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序； 任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。 【输入】输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。 【输出】输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。,转化为一条路径问题,若将盘子作为顶
20、点，且按照移动规则，将前i个尺寸的盘子移动到目标柱的最少步数作为最短路径长度，则可以将双塔问题转化为最佳路径问题。注意：由于移动规律唯一，因此决策和状态转移也是唯一的，动态规划变成递推题。,状态转移方程,按照移动规则的有序性，前i个尺寸的盘子作为阶段（2in），第i个尺寸的盘子作为状态。设fi代表i个尺寸的盘子移动到目标柱的最少步数。决策为三个移动步骤： 1、把前i-1尺寸的个盘子由起始柱移动到中间柱，移动步数为fi-1； 2、把第i个尺寸的盘子由起始柱移动到目标柱，移动步数为2； 3、把前i-1个尺寸的盘子由中间柱移动到目标柱，移动步数为fi-1。状态转移方程：,边界：f1=2 由于n的上限
21、为200，因此需要采用高精度加法和高精度乘法运算。为了确保不超时，建议按照104进制存储。,采药,【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in的第一行有两个整数T（1T 1000）和M
22、（1M100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。,转化为一条路径问题,将时间作为顶点，该段时间内采到的最大草药总价值作为路径长度的最佳值，因此可以将采药问题转化为最佳路径问题。注意： 1、每株草药可采可不采，且采摘时间任意 2、最后一株草药采摘的结束时间未定，因此最后需要枚举0，t中每段时间内采到的最大草药总价值，从中找到解,采用
23、动态规划方法解题,阶段i:依次考虑前i株草药(1im);状态j:采摘第i株草药的结束时间(xjt);决策k:什么时候采摘第i株草药可使得k+x时刻内可采到的草药总价值最大。由于草药的采摘时间任意，因此0kt-x;设aj为j时间内可采到的草药的最大总价值，第i株草药的采摘时间为x、价值为y。开始采摘第i株草药的时刻j的可能范围为0，t-x，采完第i株草药的时刻为j+x。在该时间内内可采到的草药的最大总价值aj+x=,显然，在t时间内可以采到的草药的最大总价值 ans=,var a:array0.1000of longint; /*aj为j时间内可采到的草药的最大总价值aj+x= */ t,m,i
24、,j,x,y,ans:longint;readln(t,m); /*输入采药时间和草药数*/ for i1 to t do ai -1; a0 0; for i1 to m do /*逐株采摘草药*/ readln(x,y); /*输入采摘第i株草药的时间和价值*/ for j t-x downto 0 do/*枚举开始采摘第i株草药的时刻*/ if (aj=0)and(aj+xaj+y) then aj+xaj+y ;/* for */ ans -1; /*在t时间内采到草药的最大总价值ans= */ for i 0 to t do if ansai then ans ai; writeln
25、(ans);/*输出t时间内可采到的草药的最大总价值*/ .,Chain,拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个美好的日子，拜特将军该国的统帅作了一个用以结束长期内战的决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨直接自由，而是用一根“拜特链”将拜特萨锁在墙边.该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除去它们却非常困难。 “将军，你为什么要用链子将我锁在墙边而不让我自由！”拜特萨大叫道。“拜特萨，你并未完全被链子锁住，我可以坦率的告诉你，你完全可以从栅栏上解下环。”拜特将军不忠地回答，同时他补充说，“但是，你必须在夜里工作，一个小时之
26、内完成，不能弄出任何声音，否则，我将按有关法律制罪。”。为了帮助拜特萨！链子上的环按整数1,2,n进行了编号。我们可以按照以下规则解开环：只有一个环时可以被连接到栅栏或从栅栏上拆开。 第1号环总能进行连接或拆开 如果1,.,k-1 (1=kn)环都被拆开，第k个环被连接时, 此时我们能连接或拆开第k+1个环.,写一个程序：文本文件LAN.IN描述了拜特链的构成,计算拆除拜特链上全部环的最少操作次数, 将结果写入文本文件LAN.OUT. 输入：在文本文件LAN.IN 中的第1行有一个整数n, 1=n=1000.在第2行有n个用一个空格分隔的整数 o1,o2,.,on (每个都是0或1)，如果 o
27、i=1, 那么第I个环和栅栏相连，如果 oi=0, 那么第I环没有和栅栏相连。 输出：文本文件 LAN.OUT中只包含一个整数，为解开拜特链的全部环的最少操作次数。,转化为一条路径问题,拜特链为一条长度为n的01串s。如果将s中长度为i的后缀（或前缀）看作是顶点i，将该子串全部变换到0所需的操作次数看作是初始串至顶点i的路径长度，则可以将Chain问题转化为初始串至顶点n的最短路问题。注意:通过分析解环的规律优化算法,重述题目,任意给定一个01串S，以及下面两种操作： 操作a：将S的第一个字符取反。 操作b：若S1.i1=00000，Si=1，那么将Si+1取反（1in1）同时给出一个固定的目
28、标串T = 000000。现在需要将初始串S反复执行上述两种操作，变换到目标串T。问：至少需要执行多少次操作？,譬如S = 1010,执行操作b：1110执行操作a：0110执行操作b：0100执行操作a：1100执行操作b：1000执行操作a：0000共进行了6次操作。,由规律引出最简单的算法,性质1 同一种操作不能连续两次执行。 证明：若连续执行同一操作两次，相当于没执行任何操作。所以不能将同一种操作连续两次执行。根据性质1，我们容易得到：性质2 将S变换到T的操作序列必然是： 操作序列1：abab ba或者 操作序列2：baba ba（最后执行的操作必然是a） 引出最简单的算法：分别按照
29、上述两种方法对S进行操作，得出所需得操作次数；取较小值作为答案。这种算法的效率十分低下。如果最后的结果是s，那么它的时间复杂度就是O(s)s最大可以达到2n！,要将S的每一位都变成0，显然最后一次执行的必须是操作a。故而我们可以将整个变换过程分解成：,S 100000 00000,即,将S的后n-1位全变为0。,将S的第1位变为0。,图中左列是S = 1010变到T = 0000的过程。我们如果只关心它的后n-1位，实际上是把S的后3位变换到“全零”的过程。 1、后面n-1位的变换又直接受到第一位取值的影响：当第一位为0时，后n-1位才能进行操作序列2（ba ）；当第一位为1时，后n-1位才能
30、进行操作序列1（ab）。 2、对后n-1位进行变换同样要遵行性质2（ab交替出现）。所以对后n-1位执行完一次操作a，就必须进行一次额外的操作，将原串的第一位取反；类似的，对后n-1位执行完一次操作b，也必须进行一次额外的操作，将原串中的第一位取反（即后n-1位的一次操作对应操作ba,使得后n-1位的每个状态都重复出现了两次）。,状态转移方程,S的后缀长度i(1in)为阶段，操作k为状态(k=1,2)。由于解环规律是唯一的，因此决策也是唯一的。设 fi,1通过“操作序列1”将S的后i位全部变换到0所需的最少操作次数； fi,2通过“操作序列2”将S的后i位全部变换到0所需的最少操作次数。状态转
31、移方程：当第n-i+1位是1时，有两种情况： 通过a将第n-i+1位变0，然后对后i-1位进行操作2，即 fi,1=fi-1,2*2+1； 直接对f后i-1位进行操作1，即i,2=fi-1,1*2当第n-i+1位是0时，有两种情况： 通过a将第n-i+1位变1，然后对后i-1位进行操作1，即 fi,1=fi-1,1*2+1； 直接对后i-1位进行操作2，即 fi,2=fi-1,2*2边界条件：f0,1=+，f0,2=0解：minfn, 2, fn, 1。 由于结果可能很大，所以要使用高精度运算。算法时间复杂度是O(n)。（不包括高精度运算）,漂亮打印,将当前行k的尾单词序号i作为顶点,这种情况
32、下第1行至第k行的“漂亮”标准作为路长。设 ck,i为前k行、尾单词为i时的“漂亮”标准。若第k-1行的尾单词序号为j,则第k行的单词序号为区间j+1.i，“漂亮”标准为（m-j+i-(ikj) lk）)3。由此得出 ck,i=ck-1,j+（m-j+i-(ikj) lk）)3显然，必须预先计算出单词i.单词j的长度（期间含j-i个空格）lgi,j和最后一行的起始单词序号cn,数据结构,var n,m,i,j,k,cn,ak,ai:integer; /*单词数为n,行宽为m，最后一行的起始单词序号为cn；倒数第2行的行序号为ak，该行的最后一个单词为ai*/ ans:longint; /*目前
33、为止的“漂亮”值*/ l:array0.maxof integer; /*单词的长度序列*/ c:array0.max,0.maxof longint; /*ck,i为前k行、尾单词为i时的“漂亮”标准*/ lg:array0.max,0.maxof integer; /*lgi，j为单词i.单词j的长度,含空格*/,计算lg和最后一行的起始单词序号cn,readln(f,n,m);/*读单词树n和行宽*/for i1 to n do read(f,li);/*读每个单词的长度*/l0m;/*计算lg*/for i0 to n do kli; lgi,ik; for ji+1 to n do
34、kk+lj+1; lgi,jk /*for*/ ; /*for*/for in downto 0 do if lgi,nm then break; /*计算最后一行的起始单词序号cn*/cni; inc(cn);if cnn/*若单词n的长度超过m，失败退出*/ then writeln(f0,Print is impossible.);continue ; if cn=1/*若n个单词的长度不足一行，则输出结果*/ then writeln(f0,0);writeln(f0,Line 1 : ,n);continue ; /*then*/,动态程序设计,ansmaxint;for i1 to
35、 n do c0,imaxint;c0,00;for k1 to n-1 do /*递推每一行*/for i0 to k-1 do ck,imaxint;/*前k行的状态转移方程初始化*/ for ik to n-1 do /*枚举第k行的尾单词*/ ck,imaxint; for ji-1 downto k-1 do /*枚举第k-1行的尾单词*/ if (lgj+1,i=m) and (ck-1,j+(m-lgj+1,i)3ck,i) then ck,ick-1,j+ (m-lgj+1,i)3 ;/*for*/ for icn-1 to n-1 do/*记录目前最“漂亮值”和方案*/ if
36、 ck,ians then ansck,i; akk; aii /*then*/;/*for*/,输出方案,rocedure putout(k,i:integer);/*前k行为前i个单词。输出该方案*/ var j:integer; if k=0 then exit; /*递归边界*/ for ji-1 downto k-1 do /*计算第k-1行的尾单词j*/ if (lgj+1,i=m) and (ck-1,j+ (m-lgj+1,i)3=ck,i) then break; putout(k-1,j); /*递归k-1行*/ writeln(f0,Line ,k, : ,i-j) /*
37、输出k行的单词数*/ ;/*putout*/由此得出writeln(ans); /*输出“漂亮”值*/putout(ak,ai); /*输出前ak行为前ai个单词的方案*/writeln(f0,Line ,ak+1, : ,n-ai) /*输出最后一行的单词数*/,一般有两种题型： 1、 2条最佳路径经过顶点的权和最大。需要优化状态的存储方式 2、 2条最佳路径经过的顶点数最多。,计算2条最佳路径,传纸条,【问题描述】小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈
38、了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数
39、越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的两条路径。,【输入】输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1m,n 50）。接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。【输出】输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。,由于计算的可逆性，因此设两人从左上角走至右下角。两人分别走m+n-2步
40、才能到达目的地； 阶段i：两条路径的长度（2im+n-2），满足有序性要求； 状态j,k：目前两条路径的行位置。显然，两条路径的列位置为 y1=i-j+1;y2=i-k+1（y1，y21n）由于两条路径不能重合，因此jk。最后1步前，两条路径分别在m行和m-1行 决策：第i步两条路径分别选择哪个方向走为最佳设状态转移方程fi,j,k为两条路径的当前长度为i、最后走到的行位置分别为j和k时的最大数和。,走第i步时有四种方案,情况1：两条路径向右走，即fi-1,j,k+aj,y1+ak,y2 情况2：第1条路径向下走，第2条路径向右走，即 fi-1,j-1,k+ aj,y1+ak,y2（j-1k）
41、 情况3：第2条路径向下走，第1条路径向右走，即 fi-1,j,k-1+ aj,y1+ak,y2 （jk-1） 情况4：两条路径向下走, 即 fi-1,j-1,k-1+ aj,y1+ak,y2 显然，状态转移方程为 fi,j,k=max fi-1,j,k, fi-1,j-1,kj-1k, fi-1,j,k-1 jk-1, fi-1,j-1,k-1+aj,y1+ak,y2 最后输出fm+n-2,m,m-1。,read(m,n);/*输入行数和列数*/for i1 to m do/*读数字矩阵*/ for j1 to n do read(ai,j);fillchar(f,sizeof(f),0);
42、for i2 to m+n-2 do /*延伸两条路径的长度*/ for j1 to m do /*枚举两条路径的当前行位置*/ for k1 to m do y1i-j+1;y2i-k+1; /*计算两条路径的当前列位置*/ if (not(y10)and(y20)and(y1k then fi,j,kmax(fi,j,k,fi-1,j-1,k); /*情况2：第1条路径向下走，第2条路径向右走*/ if jk-1 then fi,j,kmax(fi,j,k,fi-1,j,k-1); /*情况3：第2条路径向下走，第1条路径向右走*/ fi,j,kmax(fi,j,k,fi-1,j-1,k-
43、1); /*情况4：两条路径向下走*/ fi,j,kfi,j,k+aj,y1+ak,y2; /*取走（j,y1）和（k,y2）的数字*/ ;/*for*/ writeln(fm+n-2,m,m-1);/*输出两条路径上的最大数和*/,最佳旅行路线问题,你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市1出发，单方向从西向东经若干城市到达最东的城市n（必须到达最东的城市n）；然后再单方向从东向西飞回起点城市1（可途径若干城市）。除起点城市1外，任何城市只能访问次，起点城市1被访问次：出发一次；返回一次。除指定的航线外，不允许乘其他航线也不允许使用其他交通
44、工具。求解的问题是：给定城市表列及两城市之间的直通航线表列，请找出一条旅行路线，在满足上述限制条件下，使访问的城市数尽可能多。,旅行路线问题满足“无后效性原则”,将旅行路线拆分成两条由东到西的航线。设阶段为P1,P2，即第1条航线目前到达城市p1，第2条航线目前到达城市p2。假如阶段P1,P2可到达阶段Q1,Q2，则必须满足的条件就是:P1Q1或P2Q2。例如，阶段3,4中的道路可以加边(4,5)得出阶段3,5，而阶段3,5不可达阶段3,4，因为旅行路线要求必须严格地由左到右来旅行。,若要计算阶段i,j经过的城市数，则阶段i,k(或k,j经过的城市数已知。,因此旅行路线问题满足“无后效性原则”
45、，可以用“动态规划”算法来解决。 阶段i和j：第1条航线以城市i为尾、第2条航线以城市j为尾(1i,jn) 状态i和j ：当前两条航线的最后城市i和j 决策k：ij或者i=j=n时,i的前驱城市k； ij时j的前驱城市k。究竟应选择哪个前驱城市k才可使得两条航线经过的城市数最多。,设fi，j为从顶点1出发的两条不相交的路线分别到达顶点i与顶点j时，两路线的所需乘航线之和的最大值。有两种情况，若ij，或i=j=n时，到达i的前趋顶点k与j的两条路线的所需乘航线之和也一定最大，否则与fi，j最大矛盾。若ij时，结论同理可得。由此得出如下状态转移方程：,f i，i 无意义 (1in）最多可能的访问城
46、市数为fn，n-2（减去最东和最西的城市被重复访问的次数），时间复杂度降为O（n2）。,状态转移方程,初始化,const maxn=1001; /*顶点数的上限*/var g:array1.maxn,1.maxnof integer; /*顶点i的第k个儿子的序号为gi,k */ b:array1.maxn of integer; /*度数表，顶点i的度为di */ f:array0.maxn,0.maxn of integer; /*状态转移方程，其中fi,j为从顶点1出发的两条不相交的路线分别到达顶点i与顶点j时，两路线的所需乘航线之和的最大值*/ n:integer; /*顶点数*/pr
47、oc init; /*输入信息，构造邻接表*/var i,j:integer; readln(n); /*读顶点数*/ fillchar(b,sizeof(b),0);fillchar(g,sizeof(g),0); /*度数表和邻接表初始化*/ for i1 to n do read(j); /*读顶点i的第1个儿子*/ while j0 do inc(bi);gi,bij;read(j); /*通过循环将顶点i连出的所有边存入邻接表*/ readln ;/*for*/ fillchar(f,sizeof(f),0); /* 状态转移方程初始化*/;/*init*/,通过动态规划计算和输出最
48、多可能访问的顶点数,roc make;var i,j,k:integer; for i1 to n do /*枚举每一对顶点*/ for j1 to n do if(i=1)and (j=1)then continue; /*若i和j同为出发点，则枚举下一对顶点*/ if(ij)or(i=n)and(j=n) /*计算第一种情况*/ then for k1 to bi do /*枚举i的每个前驱顶点，计算经由前驱顶点到达顶点i和到达顶点j的最佳方案*/ if gi,ki then fi,jmax(fi,j,fgi,k,j+1); continue ; /*继续枚举下一对顶点*/ if ij /
49、*计算第二种情况：枚举j的每个前驱顶点，计算到达顶点i和经由前驱顶点到达顶点j的最佳方案，从中找出到达顶点i和到达顶点j的最佳方案*/ then for k1 to bj do if gj,kj then fi,jmax(fi,j,fi,gj,k+1); continue ; /*继续枚举下一对顶点*/ ;/*for*/ writeln(fn,n-2); /*输出最多可能访问的顶点数*/;/*make*/,对于一些阶段性明显、但不具备最优子结构特征的问题，可以考虑将指标函数值当作“状态”，计算每一个可能的状态是否可达，从而变最优化问题为能否到达指定状态的判定性问题。再借用动态规划思想，用递推方
50、式计算最佳值（即按照状态值递增的顺序寻找第一个可达的状态）。,计算一些阶段性明显、但不具备最优子结构特征的路径问题,例题 mod 4 最优路径问题,在上图中找出从第1点到第4点的一条路径，要求路径长度mod 4的余数最小。,该问题最优子结构特征,例如一条最优路径（3+2+3）mod 4=0。在它走到第2点的、第3点的路径长度mod 4的余数不一定是最小： 3 mod 40 mod 4 (3+2)mod 4(3+1)mod 4。但是我们可以把它转换成判定性问题，用递推法来解决。,设fk(sk)从第1点到第k点的长度mod 4为sk的路径是否存在的标志。显然 （边界条件）,（这里lenk,i表示从
