高中信息技术 全国青少年奥林匹克联赛教案 动态规划实例分析及程序实现

1、全国青少年信息学奥林匹克联赛动态规划实例分析及程序实现一、数字三角形（图.）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1三角形行数100；三角形中的数字为整数0，1，99；输入数据：由INPUT.TXT文件中首先读到的是三角形的行数。在例子中INPUT.TXT表示如下：573 88 1 02 7 4 44 5 2 6 5输出数据：把最大总和（整数）写入OUTPUT.TXT文件。上例为：30（图.） 二、算法分析只要对该题稍加分析，就可以得出一个结论：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路

2、径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。设：k（k）从第阶段中的点k至三角形顶点有一条最佳路径， 该路径所经过的数字的总和最大，k（k）表示为这个数字和；由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设k1阶段中某点k沿左斜线向下的点；k2阶段中某点k沿右斜线向下的点；k（k1）阶段中k1的

3、数字；k（k2）阶段中k2的数字；因而可写出顺推关系式k（k）k-1（k）k（k1），k-1（k）k（k2）0（0）；，经过一次顺推，便可分别求出由顶至底个数的条路径，在这条路径所经过的个数字和中，最大值即为正确答案。 三、程序分析根据上述顺推关系，我们编写程序如下：Program ID1P1;ConstMaxn = 100;TypeNode = RecordVal, Tot : Integer 当前格数字; 从1,1到当前格的路径所经过的数字和 End;VarList : Array 1.Maxn, 1.Maxn of Node; 计算表 N, Max, 行数, 最大总和 I, J : In

4、teger; 辅助变量 Fi : Text; 文件变量 Procedure Init;BeginAssign(Fi, INPUT.TXT); 文件名和文件变量连接 Reset(Fi); 文件读准备 Readln(Fi, N); 读三角形行数 For i := 1 to N Do 读入三角形各格的数字 For j := 1 to i Do Read(Fi, Listi, j.Val);Close(Fi)End;initProcedure Main;BeginList1, 1.Tot := List1, 1.Val; 从1,1位置开始往下顺推 For i := 2 to N DoFor j :=

5、1 to i Do BeginListi, j.Tot := -1; 从1,1至i,j的数字和初始化 If (j 1) And(Listi - 1, j - 1.Tot + Listi, j.Val Listi, j.Tot) ThenListi, j.Tot := Listi - 1, j - 1.Tot + Listi, j.Val; 若从i-1,j-1选择右斜线向下会使1,1至i,j的数字和最大,则决策该步 If (j i) And(Listi - 1, j.Tot + Listi, j.Val Listi, j.Tot) ThenListi, j.Tot := Listi - 1, j

6、.Tot + Listi, j.Val 若从i-1,j选择左斜线向下会使1,1至i,j的数字和最大,则决策该步 End; forMax := 1; 1,1至底行各点的N条路径所经过的数字和中,选择最大的一个输出 For i := 2 to N Do If ListN, i.Tot ListN, Max.Tot ThenMax := i;Writeln(ListN, Max.Tot) 输出最大总和 End; mainBeginInit; 读入数字三角形 Main 求最大总和 End.main 二、Problem : 打鼹鼠Contents: 有个n*n个格子，在m个时间点上的不定格子里有数量不等

7、的鼹鼠出现，机器人每次只能向前后左右移动一个格子，问最多机器人能打多少鼹鼠？ (n=1000, m=10000)Type: 动态规划 Difficulty: 2 Source: HNOI2004_day_*_*Solution : a) 记得学OI不到几个月，高一刚上来就做的这道题.着实郁闷了半天,有一个思路是开1000*1000 的数组乱搞忘了可以过几个来着.b) 又翻到这道题的时候是2月份了.发现 fi表示：如果机器人最后打死的老鼠是第i只，这种情况下机器人最多可以打死多少老鼠。就可以了,然后我赫然发现108 div 2次的若干基本操作是要TLE的c) 鉴于这道题郁闷的理论时间复杂度无法优

8、化，我请教了朱老师，原来动态规划枚举顺序也有其优化技巧，由于思路不是自己的，仅作简要介绍：a) (1).将更快、更容易“短路”的判断放在前面b) (2).将内部循环（j的循环）倒序，逼近最优解d) 我的计算机有点慢 总分 = 100.0第一题：mole 得分 = 100.0 用时 = 7.16smole-0(mole1.In) 结果 = 正确 得分 = 10.0 用时 = 0.01s 空间 = 0.71Mmole-1(mole2.In) 结果 = 正确 得分 = 10.0 用时 = 0.01s 空间 = 0.71Mmole-2(mole3.In) 结果 = 正确 得分 = 10.0 用时 =

9、0.02s 空间 = 0.71Mmole-3(mole4.In) 结果 = 正确 得分 = 10.0 用时 = 0.98s 空间 = 0.71Mmole-4(mole5.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71Mmole-5(mole6.In) 结果 = 正确 得分 = 10.0 用时 = 1.00s 空间 = 0.71Mmole-6(mole7.In) 结果 = 正确 得分 = 10.0 用时 = 1.05s 空间 = 0.71Mmole-7(mole8.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71Mmole

10、-8(mole9.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71Mmole-9(mole10.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71M分析设第i只老鼠在第Ti个时刻出现在(xi, yi)，T1=T2=T3=Tm。假设机器人打死了L只老鼠，不妨设这些老鼠的编号是a1, a2, , aL。显然对于任意的i(1=i=|xai+1-xai|+|yai+1-yai|。fi表示：如果机器人最后打死的老鼠是第i只，这种情况下机器人最多可以打死多少老鼠。可以列出方程：fi = maxfj+1, 11=j=|xi-xj|+|yi

11、-yj|最后求的答案就是maxfi(1=i=m) 此算法时间复杂度为O(m2)。考虑到m=10000，而时限只有1second，所以还必须进行一些代码优化。 因为ji，所以实际的循环次数只有m2/2次，也就是至多5000万左右。 我们看看下面的代码：for i := 1 to m do begin fi := 0; for j := 1 to i 1 do if (abs(xi-xj) + abs(yi-yj) fi) then fi := fj; fi:=fi+1;end; 它无疑是正确的。但是循环中的判断语句大有文章可做：上面的代码每次都铁定至少要执行3次减法、2次绝对值、1次比较运算。这

12、无疑是极度昂贵的操作代价。所以我们可以将(fjfi)这个比较“便宜”的判断条件提到前面，变成如下形式： if (fjfi) and (abs(xi-xj) + abs(yi-yj)=Ti-Tj) then这样做的好处是一旦fj=fi就可以执行“短路操作”（也就是说后面那一大截速度很慢的操作都可以避免。不过编译的时候一定要记得设成$B+） 实践证明速度是快了不少。可是对于1second的时限还是不能胜任。实战游戏经验告诉我们，机器人一般情况下不可能打完一只老鼠之后就跑到很远的地方去寻找新的猎物，肯定是一路上碰到一点老鼠就打一点。所以机器人相继打的两只老鼠的出现时间不可能相差太远。因此在方程fi

13、= maxfj+1, 11=j=|xi-xj|+|yi-yj|之中，使得i达到最优的j肯定不会和i差得太远。同时在我们的判断语句中：if (fjfi) and (abs(xi-xj) + abs(yi-yj)fi) and (abs(xi-xj) + abs(yi-yj)fi) and (abs(xi-xj)+abs(yi-yj)ans then ans:=fi; end; assign(output,mole.out); rewrite(output); writeln(ans); close(output);END. 三、最大连续子序列给出一个长度为n 的整数序列A，找出i,j 使得那一段

14、连续数之和最大。 第一行为n第二行为数列 输入样例 6 3 -5 2 4 -1 6 输出样例 11 分析： 设Fi表示Ai为最后一个元素的最大连续子序列。可得方程： Fi=max Fi-1,0+Ai时间复杂度为O（n）Program zuidalianxuzixulie;var a,s:array 0.10000 of integer; i,j,n,max:integer;begin max:=0; assign(input,lxzxl.txt); reset(input); readln(n); fillchar(s,sizeof(s),0); for i:=1 to n do begin

15、read(ai); si:=si-1 + ai; end; close(input); for i:=1 to n do for j:=1 to n do if sj - si max then max := sj - si; writeln(max);end. 四、街道问题在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。分析这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例子。通常，书上的解答是这样的：按照图中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变量xk表示当前处于这一阶段上的哪一点。这时的模型实际上已经转化成了一个特殊的多段图。用决策

16、变量uk=0表示向右走，uk=1表示向上走，则状态转移方程如下：(这里的row是地图竖直方向的行数）我们看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因而我们在实现时，一般是不会这么做的，而代之以下面方法：（这里Distance表示相邻两点间的边长）这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它的状态转移就不全是在两个阶段之间进行的了。也许这没什么大不了的，因为实践比理论更有说服力。但是，如果我们把题目扩展

17、一下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。这时，再用这种简单的方法就不太好办了。如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径不能重叠的问题。而我们回到原先标准的动态规划法，就会发现这个问题很好解决，只需要加一维状态变量就成了。即用xk=(ak,bk)分别表示两条路径走到阶段k时所处的位置，相应的，决策变量也增加一维，用uk=(xk,yk)分别表示两条路径的行走方向。状态转移时将两条路径分别考虑在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策个数：从这个例子可以看出

18、，合理地划分阶段和选择状态可以给解题带来方便。 六、花店橱窗假设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于架子上，并从1至V顺序编号，V是花瓶的数目，从左至右排列，则最左边的是花瓶1，最右边的是花瓶V。花束可以移动，并且每束花用1至F间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序，如果IJ，则令花束I必须放在花束J左边的花瓶中。 例如，假设一束杜鹃花的标识数为1，一束秋海棠的标识数为2，一束康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠

19、必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。 每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，如下表所示。 花 瓶 1 2 3 4 5 1 (杜鹃花) 7 23 -5 -24 16 2 (秋海棠) 5 21 -4 10 23 3 (康乃馨) -21 5 -4 -20 20 例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得十分难看。 为取得最佳美学效果，你必须在保持花束顺

20、序的前提下，使花束的摆放取得最大的美学值。如果有不止一种的摆放方式具有最大的美学值，则其中任何一直摆放方式都可以接受，但你只要输出任意一种摆放方式。（2）假设条件 1F100，其中F为花束的数量，花束编号从1至F。 FV100，其中V是花瓶的数量。 -50Aij50，其中Aij是花束i在花瓶j中的美学值。 （3）输入 第一行包含两个数：F，V。 随后的F行中，每行包含V个整数，Aij 即为输入文件中第（i+1 ）行中的第j个数。 （4）输出一行是程序所产生摆放方式的美学值。【样例输入1】 【样例输入2】 3 5 7 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 2

21、0 【样例输出1】 【样例输出2】 53 本题虽然是IOI99中较为简单的一题，但其中大有文章可作。说它简单，是因为它有序，因此我们一眼便可看出这题应该用动态规划来解决。但是，如何动态规划呢？如何划分阶段，又如何选择状态呢？以花束的编号来划分阶段。在这里，第k阶段布置第k束花，共有F束花，有F+1个阶段，增加第F+1阶段是为了计算的方便；状态变量xk表示第k束花所在的花瓶。而对于每一个状态xk，决策uk就是第k+1束花放置的花瓶号；最优指标函数fk(xk)表示从第k束花到第n束花所得到的最大美学值；A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F是花的总数。状态转移方程为 规划方程为

22、边界条件为： ,事实上这是一个虚拟的边界。最后要求的最大美学价值是方法1的规划方程中的允许决策空间：xk+1ukV-(F-k)+1 比较麻烦，因此有待改进。还是以花束的编号来划分阶段，第k阶段布置第k束花；状态变量xk表示第k束花所在的花瓶；注意，这里我们考虑倒过来布置花瓶，即从第F束花开始布置到第1束花。于是状态变量uk表示第k-1束花所在的花瓶；最优指标fk(xk)表示从第一束花到第k束花所获得的美学价值；A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F是花的总数。则状态转移方程为：规划方程为：增加的虚拟边界条件为：最后要求的最大美学价值是：可以看出，这种方法实质上和方法1没有区

23、别，但是允许决策空间的表示变得简单了。以花瓶的数目来划分阶段，第k个阶段决定花瓶k中是否放花；状态变量xk表示前k个花瓶中放了多少花；而对于任意一个状态xk，决策就是第xk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk(xk)表示前k个花瓶中插了xk束花，所能取得的最大美学值。注意，这里仍然是倒过来考虑。状态转移方程为规划方程为边界条件为三种不同的方法都成功地解决了问题，只不过因为阶段的划分不同，状态的表示不同，决策的选择有多有少，所以算法的时间复杂度也就不同。这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有

24、时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别。所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。七、航线设置问题描述:美丽的莱茵河畔,每边都分布着N个城市,两边的城市都是唯一对应的友好城市,现需要在友好城市开通航线以加强往来.但因为莱茵河常年大雾,如果开设的航线发生交叉现象就有可能出现碰船的现象.现在要求近可能多地开通航线并且使航线不能相交! 假如你是一个才华横溢的设计师,该如何设置友好城市间的航线使的

25、航线数又最大又不相交呢? 分析:此问题可以演化成求最大不下降序列来完成.源程序如下:program dongtai; 动态规划之友好城市航线设置问题var d:array1.1000,1.4 of integer; i,j,k,n,L,p:integer; procedure print(L:integer); 打印结果 begin writeLn(最多可设置的航线数是 : ,k); repeat writeLn(dL,1:4,dL,2:4); 输出可以设置航线的友好城市代码 L:=dL,4 untiL L=0 end;begin writeLn(输入友好城市对数: ); readLn(n);

26、 writeLn(输入友好城市对（友好城市放在同一行:); 输入 for i:=1 to n do readLn(di,1,di,2); DI，1表示起点，DI，2表示终点 for i:=1 to n do begin di,3:=1; DI，3表示可以设置的航线条数 di,4:=0 DI，4表示后继，即下一条航线从哪里开始设置，为0表示不能设置下一条航线 end;for i:=n-1 downto 1 do 从倒数第二个城市开始规划 begin L:=0; p:=0; L表示本城市后面可以设置的航线数，P表示下条航线从哪个城市开始 for j:=i+1 to n do 找出本城市后面可以设置

27、的最大航线数和小条航线到底从哪个城市开始设置 if (di,2 L) then 如果本城市I的终点小于后面城市的终点（即不相交） 并且此城市后面可以设置的航线数大于L begin L:=dj,3; 那么L等于城市J的可以设置航线数 p:=j P等于可以设置下条航线的城市代码 end; if L0 then 如果本城市后面总共可以设置的航线数0则 begin di,3:=L+1; 本城市可以设置的航线数在下个城市可以设置航线数的基础上加1 di,4:=p DI，4等于本城市后续城市的代码 end end; k:=d1,3; K为可以设置最大航线数，假设初值为第一个城市可以设置的航线数 L:=1;

28、 L为城市代码，初值为第一个城市 for i:=2 to n do 找出可以设置航线的最大值，赋值给K，同时L记下哪个可以设置最大航线数的城市代码 if di,3k then begin k:=di,3; L:=i end; for i:=1 to n do 打印结果，因为有可能有多种方案，所以只要哪个城市可以设置的航线数等于最大值K就打印结果 if di,3=k then print(i)end.八、最长不降子序列（1）问题描述设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、a(n)且a(i)a(j) (ij)例如3，18，7，14，10，12，23，41，16，24。若存在i1

29、i2i3 ie 且有a(i1)a(i2) a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。（2）算法分析根据动态规划的原理，由后往前进行搜索。1 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；2 若从a(n-1)开始查找，则存在下面的两种可能性：若a(n-1)a(n)则存在长度为1的不下降序列a(n-1)或a(n)。3 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:在a(i+1)

30、,a(i+2),a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号(3) 程序如下:（逆推法）program li1;const maxn=100;var a,b,c:array1.maxn of integer; fname:string; f:text; n,i,j,max,p:integer;begin readln(fname); assign(f,fname); reset(f); readln(f,n);+ for i:=1 to n do begin read(f,ai);

31、bn:=1; cn:=0; end; for i:= n-1 downto 1 do begin max:=0;p:=0; for j:=i+1 to n do if (aimax) then begin max:=bj;p:=j end; if p0 then begin bi:=bp+1;ci:=p end end; max:=0;p:=0; for i:=1 to n do if bimax then begin max:=bi;p:=i end; writeln(maxlong=,max); write(result is:); while p0 do begin write(ap:5

32、);p:=cp end;end.九、 背包问题背包问题有三种1.部分背包问题 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，.,Wn,它们的总价值分别为C1,C2,.,Cn.求旅行者能获得最大总价值。 解决问题的方法是贪心算法:将C1/W1,C2/W2,.Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止. 2.0/1背包 一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，.,Wn,它们的价值分别为C1,C2,.,Cn.若每种物品只有一件求旅行者能获得最大总价值。 分析说明: 显然这个题可用深度优先方

33、法对每件物品进行枚举(选或不选用0,1控制). 程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数 设 f(i，x)表示前i件物品，总重量不超过x的最优价值 则 f（i，x）=max(f(i1，x-Wi)+Ci，f（i1，x） f（n，m）即为最优解，边界条件为f（0，x）0 ，f(i,0)=0; 动态规划方法(顺推法)程序如下: 程序如下： program knapsack02; const maxm=200;maxn=30; type ar=array1.maxn of integer; var m,n,j,i:integer; c,w:ar; f:array0.maxn,0.maxm of integer; function max(x,y:integer):integer; begin if xy then max