动态规划(动态程序设计)-王建德课件.ppt

1、动态规划动态规划上海市控江中学上海市控江中学 王建德王建德讨论的问题讨论的问题1 1、动态规划的基本概念、动态规划的基本概念2 2、动态规划的基础题型、动态规划的基础题型3 3、动态规划的综合题型、动态规划的综合题型 基本概念基本概念动态程序设计是解决多阶段决策最优化问动态程序设计是解决多阶段决策最优化问题的一种思想方法。所谓题的一种思想方法。所谓“动态动态”，指的，指的是在问题的多阶段决策中，按某一顺序，是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一状态的转移，最终在变化的状态中产生一个决策序列

2、。动态规划就是为了使产生的个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。决策序列在符合某种条件下达到最优。DAGCKBNPOMJFHELI312345214323142212223344阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5问题的引出：问题的引出：P P是出发点，从是出发点，从P P到到A 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；从从P C的最短路径为的最短路径为P(C);P(C)=minP

3、(E)+5,P(F)+4；上述递推公式告诉我们，要求上述递推公式告诉我们，要求P(A)P(A)需要先求出阶段需要先求出阶段5 5中的中的P(B)P(B)和和P(C)P(C)；要求；要求 P(B)(P(B)(或者或者P(C)P(C)），又要先求出阶段），又要先求出阶段4 4中的中的 P(D)P(D)和和 P(E)(P(E)(或或P(F)P(F)和和P(E)P(E)（倒推）（倒推）显然，要依照上述递推过程求解，需要倒过来，从显然，要依照上述递推过程求解，需要倒过来，从P(P)P(P)出发，先求出第一阶段的出发，先求出第一阶段的P(O)P(O)和和P(N)P(N)，再求第二阶段的，再求第二阶段的P(

4、K)P(K)，P(L)P(L)，P(M)P(M)；，最后得到，最后得到P(A)P(A)（顺推）。（顺推）。h30h31h32h20h21h22h10h11h12h00h01h02v20v21v22v23v10v11v12v13v00v01v02v03(3,3)0213213yx数据结构数据结构将每条路经的长度存在数组中东西方向上的道路长度将每条路经的长度存在数组中东西方向上的道路长度存在两维数组存在两维数组h43h43中中,规定数组的第一维为行号，规定数组的第一维为行号，第二维为列号。第二维为列号。h43=3,2,3,2,1,4,3,4,5,3,1,2;南北方向上道路长度存至数组南北方向上道路

5、长度存至数组v34v34中，也规定中，也规定第一维为行号，第二维为列号。第一维为行号，第二维为列号。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=min3+1,2+2=4 P02=P01+h1

6、0=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=min P21+v21,P30+h30=min5+2,7+3=7 阶段阶段5:P23=min P13+v13,P22+h22=min9+4,7+5=1

7、2 P32=min P22+v22,P31+h31=min7+2,7+1=8最后最后:P33=min P23+v23,P32+h32=min/*12+3,8+2=10综上，数组综上，数组P P的通项表示为的通项表示为Pij=min(pi-1j+vi-1j),(pij-1+hij-1)Pij=min(pi-1j+vi-1j),(pij-1+hij-1)(i,j0)(i,j0)P0j=P0j-1+h0j-1P0j=P0j-1+h0j-1(i=0,j0)(i=0,j0)Pi0=Pi-10+vi-10Pi0=Pi-10+vi-10(i0,j=0)(i0,j=0)P P数组数据数组数据圆圈内为路口对圆圈

8、内为路口对P 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)w

9、riteln;/*for*/程序程序 阶段：据空间顺序或时间顺序对问题的求解划分阶段。阶段：据空间顺序或时间顺序对问题的求解划分阶段。状态：描述事物的性质，不同事物有不同的性质，因状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。阶段的。决策：根据题意要求，对每个阶段所做出的某种选择决策：根据题意要求，对每个阶段所做出的某种选择性操作。性操作。状态转移方程：用数学公式描述与阶段相关的状态间状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。的演变规律。多阶段决策过程：将所研究的过程划分为若

10、干个相互多阶段决策过程：将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。前一个决策确定以后，常常会影响下一个阶段的决策。动态规划的几个要素动态规划的几个要素 “最优性原理最优性原理”：不论初始状态和第一步：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。产生的新状态，构成一个最优决策序列。最优决策序列的子序列，一定是局部最优最优决策序列的子序列，一定是局部最优决策子序列。注意包含有非

11、局部最优的决策子决策子序列。注意包含有非局部最优的决策子序列，一定不是最优决策序列序列，一定不是最优决策序列,例如贪心法。例如贪心法。动态规划的依据动态规划的依据“最优性原理最优性原理”动态规划的指导思想动态规划的指导思想在做每一步决策时，列出各种可能的局部解，之后在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度

12、看），效率会十分高。限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。但它又不同于贪心法。贪心法贪心法:产生一个按贪心策略形成的判定序列，该产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的，因为有些问题不符合序列不保证解是全局最优的，因为有些问题不符合最优性原理。最优性原理。动态规划动态规划:产生许多判定序列，再按最优性原理对产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列这些序列加以筛选，去除那些非局部最优的子序列2 2、动态规划的基础题型、动态规划的基础题型1 1、路径问题、路径问题2 2、0101背包问题背包问题3 3、求最佳子序

13、列问题、求最佳子序列问题4 4、双重动态规划、双重动态规划路径问题的讨论路径问题的讨论问题的一般形式：问题的一般形式：1 1、计算所有路径方案、计算所有路径方案 2 2、计算一条最佳路径、计算一条最佳路径 3 3、计算两条最佳路径（多进程的最优化决策）、计算两条最佳路径（多进程的最优化决策）一般方法：一般方法：按照出发点走出的步数划分阶段，将当前步可达按照出发点走出的步数划分阶段，将当前步可达的顶点集定义为状态，当前步如何走定义为决策。的顶点集定义为状态，当前步如何走定义为决策。注意：注意：1 1、可能需要将原题转化为路径问题、可能需要将原题转化为路径问题 2 2、如果最佳路径问题不满足最优子

14、结构特征特、如果最佳路径问题不满足最优子结构特征特征的话，可以转化为判定性问题求解。征的话，可以转化为判定性问题求解。一、计算所有方案一、计算所有方案 对于一些阶段性强、但不属于最优化的问题，是对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态规划方法呢？如果我们可以找出否也可以借助动态规划方法呢？如果我们可以找出状态转移的关系，并在状态转移方程状态转移的关系，并在状态转移方程),()()(1,111Gsuwufoptsfkksukkkkkk中去掉最佳性要求中去掉最佳性要求optopt（minmin或或maxmax），将扩展子状），将扩展子状态的所有行动作为决策，则可以例举出由初始状态

15、的所有行动作为决策，则可以例举出由初始状态至目标状态的所有方案。显然，在计数类问题态至目标状态的所有方案。显然，在计数类问题中使用这种方法要比回溯法等搜索算法简捷许多。中使用这种方法要比回溯法等搜索算法简捷许多。例题 过河卒 如图，如图，A A点有一个过河卒，需要走到目标点有一个过河卒，需要走到目标B B点。卒行走的规则：可以向下、或者向右。点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上同时在棋盘上的任一点有一个对方的马（如上图的图的C C点）点）,该马所在的点和所有跳跃一步可达的点该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图称为对方马的控制点

16、。例如上图C C点上的马可以控点上的马可以控制制8 8个点（图中的个点（图中的P1P1，P2.P8P2.P8）。卒不能通过对方）。卒不能通过对方马的控制点。马的控制点。棋盘用坐标表示，棋盘用坐标表示，A A点（点（0 0，0 0）、）、B B点（点（n n，m m）(n,m(n,m为不超过为不超过2020的整数的整数,并由键盘输入并由键盘输入)，同样马的，同样马的位置坐标是需要给出的（约定：位置坐标是需要给出的（约定：CACA，同时，同时CBCB）。现在要求你计算出卒从）。现在要求你计算出卒从A A 点能够到达点能够到达B B点点的路径的条数。的路径的条数。输输 入：键盘输入入：键盘输入B B

17、点的坐标点的坐标(n,m)(n,m)以及对方马的坐以及对方马的坐标（标（X X，Y Y）输输 出：屏幕输出一个整数（路径的条数）。出：屏幕输出一个整数（路径的条数）。按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（0，0）或（n,m）为控制点，则输出路径数为0。设constconstmove:array1.8,1.2of integer /move:array1.8,1.2of integer /*movek movek，1.21.2为马沿为马沿k k方向跳跃一步的水平增量和垂直增量方向跳跃一步的

18、水平增量和垂直增量*/=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)1,-2),(-2,1),(-2,-1)；varvar list:array-1.20,-1.20of comp list:array-1.20,-1.20of comp；/*listi,jlisti,j 为卒从为卒从(0,0)(0,0)到到(i,j)(i,j)的路径数的路径数*/can:array0.20,0.20of boolean can:array0.20,0.20of boolea

19、n；/*cani,jcani,j 为允许卒通行为允许卒通行(i,j(i,j)的标志的标志*/1 1、计算对方马的控制点、计算对方马的控制点设马的初始位置为（设马的初始位置为（x,yx,y）。按照下述方）。按照下述方式计算式计算cancan序列序列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)/*若（

20、若（j,k）在界内，则）在界内，则为控制点为控制点*/then canj,kfalse；/*for*/if(not can0,0)or(not cann,m)/*若卒的起点和终点为若卒的起点和终点为控制点，则输出路径数控制点，则输出路径数0*/then writeln(0)else计算和输出卒从（计算和输出卒从（0，0）走到（）走到（n,m）点的路径数）点的路径数listn,m；/*else*/我们按照由上而下、由左而右的顺序，将卒可能到达的每一我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（个位置（i,ji,j）(0in(0in，0jm)0jm)设为阶段和状态。设为阶段和状态。首

21、先，将卒的出发点（首先，将卒的出发点（0 0，0 0）的路径数设为）的路径数设为1 1，该位置设为控，该位置设为控制点（制点（list0,01;can0,0 falslist0,01;can0,0 fals）。然后从（）。然后从（0 0，0 0）出发，）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数数:若（若（i i，j j）为可行点，则走前位置（）为可行点，则走前位置（i-1,ji-1,j）和（）和（i,j-1i,j-1）的路）的路径数加起来，即为从（径数加起来，即为从（0 0，0 0）走到（）走到（i i，j j）的

22、路径数，即）的路径数，即listi,j=listi-1,j+listi,j-1listi,j=listi-1,j+listi,j-1 （i i，j j）非控制点）非控制点依次类推，最后得出的依次类推，最后得出的listn,mlistn,m即为问题的解。由此得出算法：即为问题的解。由此得出算法：fillchar(list,sizeof(list),0)；/*路径数序列初始化路径数序列初始化*/list0,01；can0,0 false；/*卒从（卒从（0，0）出发的路径数）出发的路径数为为1，该位置不再允许卒通行，该位置不再允许卒通行*/for i0 to n do /*按照由上而下、由左而右计

23、按照由上而下、由左而右计算从算从(0,0)到每个可行点的路径数到每个可行点的路径数*/for j0 to m do if cani,jthen listi,jlisti-1,j+listi,j-1；输出卒从（输出卒从（0，0）走到（）走到（n,m）点的路径条数）点的路径条数listn,m；2 2、计算和输出卒从（、计算和输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条数）点的路径条数计算一条最佳路径计算一条最佳路径以路径长度划分阶段，从出发点走以路径长度划分阶段，从出发点走i i步可达的顶点集合为状步可达的顶点集合为状态。设态。设fi,jfi,j 为到达阶段为到达阶段i i的顶

24、点的顶点j j的最优解。的最优解。枚举第枚举第i-1i-1阶段中与状态阶段中与状态j j相连的状态相连的状态k,k,其子问题的最优其子问题的最优解解 fi-1,k+fi-1,k+状态状态k k至状态至状态j j的决策代价的决策代价w wk,jk,j即为阶段即为阶段i i的状态的状态j j的一种方案。枚举了所有可能方案后即可得出的一种方案。枚举了所有可能方案后即可得出fi,jfi,j。fi-1,k1Wk1,jfi-1,k2Wk2,jfi-1,kpWkp,j寻宝游戏寻宝游戏 分析分析在“藏宝图”中寻求一条含len个顶点的路径，使得(1klen)(xk,yk)-ak)2最小。数据结构数据结构cons

25、t ex:array1.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;/*数列与表格的接近程度数列与表格的接近程度*/输入

26、信息，计算c0的初始值readln(f,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 /*状态状态

27、:当前位置当前位置*/for j1 to m do c1i,jmaxint;for l1 to 4 do /*决策决策:选择最佳移前位置选择最佳移前位置*/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,j=0)and(aj+xaj+y)then aj+x

28、aj+y;/*for*/ans -1;/*在在t时间内采到草药的最大总价值时间内采到草药的最大总价值ans=*/for i 0 to t do if ansai then ans ai;writeln(ans);/*输出输出t时间内可采到的草药的最大总价值时间内可采到的草药的最大总价值*/.0max0jayjaxtjmax0iatiChain 拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个美好的日子，拜特将军该国的统帅作了一个用以结束长期内战的美好的日子，拜特将军该国的统帅作了一个用以结束长期内战的决定，释放被关押的反对派。

29、然而，他并未让反对派的领袖拜特萨决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨直接自由，而是用一根直接自由，而是用一根“拜特链拜特链”将拜特萨锁在墙边将拜特萨锁在墙边.该链子由很该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除去它们却非常困难。除去它们却非常困难。“将军，你为什么要用链子将我锁在墙边而不让我自由！将军，你为什么要用链子将我锁在墙边而不让我自由！”拜特拜特萨大叫道。萨大叫道。“拜特萨，你并未完全被链子锁住，我可以坦率的告诉拜特萨，你并未完全被链子锁住，我可以坦率的告诉你，你完全可以从栅栏上

30、解下环。你，你完全可以从栅栏上解下环。”拜特将军不忠地回答，同时他拜特将军不忠地回答，同时他补充说，补充说，“但是，你必须在夜里工作，一个小时之内完成，不能弄但是，你必须在夜里工作，一个小时之内完成，不能弄出任何声音，否则，我将按有关法律制罪。出任何声音，否则，我将按有关法律制罪。”。为了帮助拜特萨！。为了帮助拜特萨！链子上的环按整数链子上的环按整数1,2,1,2,n,n进行了编号。我们可以按照以下规则解进行了编号。我们可以按照以下规则解开环：开环：只有一个环时可以被连接到栅栏或从栅栏上拆开。只有一个环时可以被连接到栅栏或从栅栏上拆开。第第1 1号环总能进行连接或拆开号环总能进行连接或拆开 如

31、果如果1,.,k-1(1=kn)1,.,k-1(1=kn)环都被拆开，第环都被拆开，第k k个环被连接时个环被连接时,此时我们能连接或拆开第此时我们能连接或拆开第k+1k+1个环个环.写一个程序：文本文件写一个程序：文本文件LAN.INLAN.IN描述了拜特链的构成描述了拜特链的构成,计算拆除拜特链上全部环的最少操作次数计算拆除拜特链上全部环的最少操作次数,将结果将结果写入文本文件写入文本文件LAN.OUT.LAN.OUT.输入：在文本文件输入：在文本文件LAN.IN LAN.IN 中的第中的第1 1行有一个整数行有一个整数n,1=n=1n,1=nm then break;/*计算最后一行的计

32、算最后一行的起始单词序号起始单词序号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 n do c0,imaxint;c0,00;for k1 to n-1 do /*递推每一

33、行递推每一行*/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 ck,ians then

34、ansck,i;akk;aii/*then*/;/*for*/输出方案输出方案procedure 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)/*输出输

35、出k行的单词数行的单词数*/;/*putout*/由此得出由此得出writeln(ans);/*输出输出“漂亮漂亮”值值*/putout(ak,ai);/*输出前输出前ak行为前行为前ai个单词的方案个单词的方案*/writeln(f0,Line,ak+1,:,n-ai)/*输出最后一行的单词数输出最后一行的单词数*/一般有两种题型：1、2 2条最佳路径经过顶点的权和最大。条最佳路径经过顶点的权和最大。需要优化状态的存储方式需要优化状态的存储方式 2 2、2 2条最佳路径经过的顶点数最多。条最佳路径经过的顶点数最多。计算计算2 2条最佳路径条最佳路径传纸条传纸条【问题描述】小渊和小轩是好朋友也

36、是同班同学，他们在一起总【问题描述】小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m m行行n n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标角，坐标(1,1)(1,1)，小轩坐在矩阵的右下角，

37、坐标，小轩坐在矩阵的右下角，坐标(m,n(m,n)。从小渊传。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之条的时候帮忙，那么在小轩递

38、给小渊的时候就不会再帮忙。反之亦然。亦然。还有一件事情需要注意，全班每个同学愿意帮忙的好感度有还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用高有低（注意：小渊和小轩的好心程度没有定义，输入时用0 0表表示），可以用一个示），可以用一个0-1000-100的自然数来表示，数越大表示越好心。的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最到来回两条传递路径，使得这两条路径上同学的好心程度之

39、和最大。现在，请你帮助小渊和小轩找到这样的两条路径。大。现在，请你帮助小渊和小轩找到这样的两条路径。【输入】输入文件【输入】输入文件message.inmessage.in的第一行有的第一行有2 2个个用空格隔开的整数用空格隔开的整数m m和和n n，表示班里有，表示班里有m m行行n n列列（1 1m,n m,n 50 50）。接下来的）。接下来的m m行是一个行是一个m m*n n的矩阵，矩阵中第的矩阵，矩阵中第i i行行j j列的整数表示坐在第列的整数表示坐在第i i行行j j列的学生的好心程度。每行的列的学生的好心程度。每行的n n个整数之间个整数之间用空格隔开。用空格隔开。【输出】输

40、出文件【输出】输出文件message.outmessage.out共一行，包含共一行，包含一个整数，表示来回两条路上参与传递纸条的一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。学生的好心程度之和的最大值。由于计算的可逆性，因此设两人从左上角走至右下角。两人分别走m+n-2步才能到达目的地；阶段i：两条路径的长度（2im+n-2），满足有序性要求；状态j,k：目前两条路径的行位置。显然，两条路径的列位置为 y1=i-j+1;y2=i-k+1（y1，y21n）由于两条路径不能重合，因此jk。最后1步前，两条路径分别在m行和m-1行 决策：第i步两条路径分别选择哪个方向走为最佳

41、设状态转移方程fi,j,k为两条路径的当前长度为i、最后走到的行位置分别为j和k时的最大数和。走第走第i i步时有四种方案步时有四种方案 情况情况1 1：两条路径向右走，即fi-1,j,k+aj,y1+ak,y2 情况情况2 2：第1条路径向下走，第2条路径向右走，即 fi-1,j-1,k+aj,y1+ak,y2（j-1k）情况情况3 3：第2条路径向下走，第1条路径向右走，即 fi-1,j,k-1+aj,y1+ak,y2（jk-1）情况情况4 4：两条路径向下走,即 fi-1,j-1,k-1+aj,y1+ak,y2 显然，状态转移方程为 fi,j,k=max fi-1,j,k,fi-1,j-

42、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);for i2 to m+n-2 do /*延伸两条路径的长度延伸两条路径的长度*/for j1 to m do /*枚举两条路径的当前行位置枚举两条路径的当前行位置*/for k1 to m do y1i-j+1;y2i-k+1;/*计算两条路径的计算两条

43、路径的当前列位置当前列位置*/if(not(y10)and(y20)and(y1=n)and(y2=n)or(j=k)then continue;/*若两条路径的若两条路径的当前列位置越出界外或者同处当前列位置越出界外或者同处一行的话，则继续枚举一行的话，则继续枚举*/fi,j,kmax(fi,j,k,fi-1,j,k);/*情况情况1：两条路径向右走：两条路径向右走*/if j-1k then fi,j,kmax(fi,j,k,fi-1,j-1,k);/*情况情况2：第：第1条路径向下走，条路径向下走，第第2条路径向右走条路径向右走*/if jk-1 then fi,j,kmax(fi,j,

44、k,fi-1,j,k-1);/*情况情况3：第：第2条路径向下走，条路径向下走，第第1条路径向右走条路径向右走*/fi,j,kmax(fi,j,k,fi-1,j-1,k-1);/*情况情况4：两条路径向下走：两条路径向下走*/fi,j,kfi,j,k+aj,y1+ak,y2;/*取走（取走（j,y1）和（和（k,y2）的数字）的数字*/;/*for*/writeln(fm+n-2,m,m-1);/*输出两条路径上的最大数和输出两条路径上的最大数和*/最佳旅行路线问题最佳旅行路线问题 你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市1出发，单方向从西向

45、东经若干城市到达最东的城市n（必须到达最东的城市n）；然后再单方向从东向西飞回起点城市1（可途径若干城市）。除起点城市1外，任何城市只能访问次，起点城市1被访问次：出发一次；返回一次。除指定的航线外，不允许乘其他航线也不允许使用其他交通工具。求解的问题是：给定城市表列及两城市之间的直通航线表列，请找出一条旅行路线，在满足上述限制条件下，使访问的城市数尽可能多。旅行路线问题满足旅行路线问题满足“无后效性原则无后效性原则”将旅行路线拆分成两条由东到西的航线。设阶段为P1,P2，即第1条航线目前到达城市p1，第2条航线目前到达城市p2。假如阶段P1,P2可到达阶段Q1,Q2，则必须满足的条件就是:P

46、1Q1或P2j或者i=j=n时,i的前驱城市k；ij，或i=j=n时，到达i的前趋顶点k与j的两条路线的所需乘航线之和也一定最大，否则与fi，j最大矛盾。若ij时，结论同理可得。由此得出如下状态转移方程：)(1,max)(1,max,0 1,1),(),(jikifnjijijkfjiffEjkjkEikik且且或f i，i 无意义(1in）最多可能的访问城市数为fn，n-2（减去最东和最西的城市被重复访问的次数），时间复杂度降为O（n2）。状态转移方程状态转移方程初始化初始化const maxn=1001;/*顶点数的上限顶点数的上限*/var g:array1.maxn,1.maxnof

47、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;/*顶点数顶点数*/proc init;/*输入信息，构造邻接表输入信息，构造邻接表*/var i,j:integ

48、er;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*/通过动态规划计算和输出最多

49、可能访问的顶点数通过动态规划计算和输出最多可能访问的顶点数proc 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的最佳方案的最佳方

50、案*/if gi,ki then fi,jmax(fi,j,fgi,k,j+1);continue;/*继续枚举下一对顶点继续枚举下一对顶点*/if ij /*计算第二种情况：枚举计算第二种情况：枚举j的每个前驱顶点，计算到达顶点的每个前驱顶点，计算到达顶点i和经由和经由前驱顶点到达顶点前驱顶点到达顶点j的最佳方案，从中找出到达顶点的最佳方案，从中找出到达顶点i和到达顶点和到达顶点j的最佳方案的最佳方案*/then for k1 to bj do if gj,k0 mod 43 mod 40 mod 4 (3+2)mod 4(3+1)mod 4 (3+2)mod 4(3+1)mod 4。但是我