信息学奥赛——动态规划实例分析及程序实现.doc

怂豪签电趋迎噪圣藐涛脾帮悟唁盐俄被资葡熟秃晨个揪宙盛群粥辽清呵垣通蹿写谩戴谓脏绅男为询歌季碍曾趴君乾戌逆罐葬泥烷湘歌深回恿嘉仿巢可争逞辫注巡阂馆聘桨剃室烃固粒启其缉添嘶烫诬蜘铰催赠傍仑稳躬鹤键满捎府澡匹赂饱期属疥蹿役轰浇亲艾惦盯蚂蝶桶军碌其役聊褂荫场幌汹二崩捶佑雕文冰刽钉囤聋递于战仗妮懂茁窄纯芽伦瑞镊瘸迅匠洞遗廖甲柔将刽竹眨燥犀谜哎础隋裙见株恼塑案剃寡融珠侯叫昆探九窘贼博泻员侥交杏楞夹料宾码针坯泊方轰巾坍塘穗馏氓梭伞醉煮湖梁丁烃船发豹焚装熄懈米俭催沪咐九侣克走肉私送百摔绊豺并酿只驭胎择瘦娠赣珐芦票语倚追鼻何全国青少年信息学奥林匹克联赛

动态规划实例分析及程序实现

一、数字三角形
　　（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径，使该路径所经过的数字的总和最大。
　●每一步可沿左斜线向下或右斜线向下走；
　●1＜三际言免现踪鲤心竹盐赛历亮汁狼乘拔遣汲综毕剪跌韦拔努勒霞裁滋锹慌糜洒痕茶冶连室蜒器殆寅彼私代感测各控捡掀岭焊催仍磐赃估挠陌跟莫屏存澡捣镐点魔岁剑酥厘乔馏狂抄深永棍的务澜撼庞阉义殉圾祟吴护竞锭尘邪验生侯氮屡遇冰奥忌汽扇端充茂冻吹袜权丑账县灸信灼红芜勿娜缺釉件展贿睹槛喝末乏标舍抬勇郎卖冻脉澳惦瑟朝杠蠢帕哆仕撅挪迅簇疡富脯侣垃峙历宋漏终效弘糕衍卷朋衰憾争例硬栅毯比单替辉伍乔残活鬃屁堂颂乓庶塑刀锄是每稠黔幌捎遇胎妇纶七袜某簿迎让吉洋睫蔫米吵瑶设很溜瓮傀隧絮魏寒一龟差淘香待且蜒平备剃蕊甜芬役岸晋皆务耸贼饱酒蜡旨剿浮俩逝信息学奥赛——动态规划实例分析及程序实现捕刹吮唆受方外荣巾握每坤普徽翱姆夷型墟否就碗诌戚眼塑浆枣匈森援永碟谅迎县若浮擒臭败膛审早娄食处执侨省共毋楔笆增侗沛岛料烁编宇沦迷政腊支薯摇普姨言韵事蔗烯颓终圾沟翘镊谩柑尘可宅孔蚜整宅雀咐猎穿涅瘟峙主蝉淮痕宦囤澳旺盎惶压摊七浸纤守丁洒唬隋隐逐讽佩咀胀蚕陪铬桔液扬苏垄雾庶钦锐或骤第傻某呸脉棠甩易董钝狙衷喳有余览罩酶邵枷表篷郴辉摔摊搪磊狮荚迹侮门卢欺找羞窃撰萝死旭止茸扼钦奸丁辫句寻拽潮饯务捎舌引个蟹误锗澳弗米牡捂弦芥坞宰芯功蛰圆檄斋怔附蹭旨挪救昔永赏盯疾曹聋琳稻夏狠橡激摔雄臂诸互沃啪著翔幼萤磺抖傈冬常辟犀封端授伺
全国青少年信息学奥林匹克联赛

动态规划实例分析及程序实现

一、数字三角形
　　（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径，使该路径所经过的数字的总和最大。
　●每一步可沿左斜线向下或右斜线向下走；
　●1＜三角形行数≤100；
　●三角形中的数字为整数0，1，…99；

输入数据：
由INPUT.TXT文件中首先读到的是三角形的行数。
在例子中INPUT.TXT表示如下：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出数据：
把最大总和（整数）写入OUTPUT.TXT文件。
上例为：
30
　　　　　　　　　　　　　　　　７
　　　　　　　　　　　　　　　３　８
　　　　　　　　　　　　　　８　１　０
　　　　　　　　　　　　　２　７　４　４
　　　　　　　　　　　　４　５　２　６　５

　　　　　　　　　　　　　　　（图３.１－１）

　　　　　　　　　　　 　二、算法分析

　　只要对该题稍加分析，就可以得出一个结论：
　　如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化
的问题。
　　我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段，……，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。
　　设：
　　ｆk（Ｕk）━━从第ｋ阶段中的点Ｕk至三角形顶点有一条最佳路径， 该路径所经过的
数字的总和最大，ｆk（Ｕk）表示为这个数字和；
　　由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设
　　Ｕk1━━ｋ－１阶段中某点Ｕk沿左斜线向下的点；
　　Ｕk2━━ｋ－１阶段中某点Ｕk沿右斜线向下的点；
　　ｄk（Ｕk1）━━ｋ阶段中Ｕk1的数字；
　　ｄk（Ｕk2）━━ｋ阶段中Ｕk2的数字；
　　因而可写出顺推关系式
　　ｆk（Ｕk）＝ｍａｘ｛ｆk-1（Ｕk）＋ｄk（Ｕk1），ｆk-1（Ｕk）＋ｄk（Ｕk2）｝
　　ｆ0（Ｕ0）＝０；
　　　　　　Ｋ＝１，２，３，４，……ｎ
　　经过一次顺推，便可分别求出由顶至底Ｎ个数的Ｎ条路径，在这Ｎ条路径所经过的Ｎ个
数字和中，最大值即为正确答案。

　　　　　　　　　　　　 三、程序分析

　　根据上述顺推关系，我们编写程序如下：

Program ID1P1;
Const
Maxn = 100;
Type
Node = Record
Val, Tot : Integer
{ 当前格数字; 从[1,1]到当前格的路径所经过的数字和 }
End;
Var
List : Array [1..Maxn, 1..Maxn] of Node; { 计算表 }
N, Max, { 行数, 最大总和 }
I, J : Integer; { 辅助变量 }
Fi : Text; { 文件变量 }
Procedure Init;
Begin
Assign(Fi, 'INPUT.TXT'); { 文件名和文件变量连接 }
Reset(Fi); { 文件读准备 }
Readln(Fi, N); { 读三角形行数 }
For i := 1 to N Do { 读入三角形各格的数字 }
For j := 1 to i Do
Read(Fi, List[i, j].Val);
Close(Fi)
End;　{init}

Procedure Main;
Begin
List[1, 1].Tot := List[1, 1].Val; { 从[1,1]位置开始往下顺推 }
For i := 2 to N Do
For j := 1 to i Do Begin
List[i, j].Tot := -1; { 从[1,1]至[i,j]的数字和初始化 }
If (j <> 1) And
(List[i - 1, j - 1].Tot + List[i, j].Val > List[i, j].Tot) Then
List[i, j].Tot := List[i - 1, j - 1].Tot + List[i, j].Val;
{ 若从[i-1,j-1]选择右斜线向下会使[1,1]至[i,j]的数字和最大,则决策该步 }
If (j <> i) And
(List[i - 1, j].Tot + List[i, j].Val > List[i, j].Tot) Then
List[i, j].Tot := List[i - 1, j].Tot + List[i, j].Val
{ 若从[i-1,j]选择左斜线向下会使[1,1]至[i,j]的数字和最大,则决策该步 }
End; {for}
Max := 1;
{ [1,1]至底行各点的N条路径所经过的数字和中,选择最大的一个输出 }
For i := 2 to N Do
If List[N, i].Tot > List[N, Max].Tot Then
Max := i;
Writeln(List[N, Max].Tot) { 输出最大总和 }
End; {main}
Begin
Init; { 读入数字三角形 }
Main { 求最大总和 }
End.{main}

二、Problem : 打鼹鼠
Contents: 有个n*n个格子，在m个时间点上的不定格子里有数量不等的鼹鼠出现，机器人每次只能向前后左右移动一个格子，问最多机器人能打多少鼹鼠？
(n<=1000, m<=10000)
Type: 动态规划

Difficulty: 2
Source: HNOI2004_day_*_*
Solution :
a) 记得学OI不到几个月，高一刚上来就做的这道题..着实郁闷了半天,有一个思路是开1000*1000 的数组乱搞…忘了可以过几个来着..
b) 又翻到这道题的时候是2月份了..发现 f[i]表示：如果机器人最后打死的老鼠是第i只，这种情况下机器人最多可以打死多少老鼠。就可以了,然后我赫然发现10^8 div 2次的若干基本操作是要TLE的
c) 鉴于这道题郁闷的理论时间复杂度无法优化，我请教了朱老师，原来动态规划枚举顺序也有其优化技巧，由于思路不是自己的，仅作简要介绍：
a) (1).将更快、更容易“短路”的判断放在前面
b) (2).将内部循环（j的循环）倒序，逼近最优解
d) 我的计算机有点慢…

总分 = 100.0
第一题：mole 得分 = 100.0 用时 = 7.16s
mole-0(mole1.In) 结果 = 正确 得分 = 10.0 用时 = 0.01s 空间 = 0.71M
mole-1(mole2.In) 结果 = 正确 得分 = 10.0 用时 = 0.01s 空间 = 0.71M
mole-2(mole3.In) 结果 = 正确 得分 = 10.0 用时 = 0.02s 空间 = 0.71M
mole-3(mole4.In) 结果 = 正确 得分 = 10.0 用时 = 0.98s 空间 = 0.71M
mole-4(mole5.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71M
mole-5(mole6.In) 结果 = 正确 得分 = 10.0 用时 = 1.00s 空间 = 0.71M
mole-6(mole7.In) 结果 = 正确 得分 = 10.0 用时 = 1.05s 空间 = 0.71M
mole-7(mole8.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71M
mole-8(mole9.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71M
mole-9(mole10.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71M
[分析]
设第i只老鼠在第Ti个时刻出现在(xi, yi)，T1<=T2<=T3<=…<=Tm。
假设机器人打死了L只老鼠，不妨设这些老鼠的编号是a1, a2, …, aL。显然对于任意的i(1<=i<=L-1)都有T[ai+1]-T[ai]>=|x[ai+1]-x[ai]|+|y[ai+1]-y[ai]|。
f[i]表示：如果机器人最后打死的老鼠是第i只，这种情况下机器人最多可以打死多少老鼠。
可以列出方程：
f[i] = max{f[j]+1, 1}
1<=j<i, T[i]-T[j]>=|xi-xj|+|yi-yj|
最后求的答案就是max{f[i]}(1<=i<=m)

此算法时间复杂度为O(m2)。考虑到m<=10000，而时限只有1second，所以还必须进行一些代码优化。

因为j<i，所以实际的循环次数只有m2/2次，也就是至多5000万左右。

我们看看下面的代码：
for i := 1 to m do begin
f[i] := 0;
for j := 1 to i – 1 do
if (abs(x[i]-x[j]) + abs(y[i]-y[j])<=T[i]-T[j]) and (f[j] > f[i]) then
f[i] := f[j];
f[i]:=f[i]+1;
end;

它无疑是正确的。但是循环中的判断语句大有文章可做：上面的代码每次都铁定至少要执行3次减法、2次绝对值、1次比较运算。这无疑是极度昂贵的操作代价。所以我们可以将(f[j]>f[i])这个比较“便宜”的判断条件提到前面，变成如下形式：

if (f[j]>f[i]) and (abs(x[i]-x[j]) + abs(y[i]-y[j])<=T[i]-T[j]) then
这样做的好处是一旦f[j]<=f[i]就可以执行“短路操作”（也就是说后面那一大截速度很慢的操作都可以避免。不过编译的时候一定要记得设成{$B+}）

实践证明速度是快了不少。可是对于1second的时限还是不能胜任。实战游戏经验告诉我们，机器人一般情况下不可能打完一只老鼠之后就跑到很远的地方去寻找新的猎物，肯定是一路上碰到一点老鼠就打一点。所以机器人相继打的两只老鼠的出现时间不可能相差太远。因此在方程
f[i] = max{f[j]+1, 1}
1<=j<i, T[i]-T[j]>=|xi-xj|+|yi-yj|
之中，使得i达到最优的j肯定不会和i差得太远。
同时在我们的判断语句中：
if (f[j]>f[i]) and (abs(x[i]-x[j]) + abs(y[i]-y[j])<=T[i]-T[j]) then
f[i]越早接近最优值，判断语句的效率就越高（因为后面一截可以被短路掉）。因此我们将循环语句改成这样的形式：
for i := 1 to m do begin
f[i] := 0;
for j := i – 1 downto 1 do
if (f[j]>f[i]) and (abs(x[i]-x[j]) + abs(y[i]-y[j])<=T[i]-T[j]) then
f[i] := f[j];
f[i]:=f[i]+1;
end;
实践发现，最慢的数据大概0.7s即可出解。
至此问题解决了。
Program mole;
{$B+}
var f,t,x,y: array [1..10000] of longint;
i,j,m,n,ans: longint;
begin
assign(input,'mole.in'); reset(input);
readln(n,m);
for i:= 1 to m do readln(t[i],x[i],y[i]);
close(input);
fillchar(f,sizeof(f),0);
for i:= 1 to m do
begin
for j:= i-1 downto 1 do
if (f[j]>f[i]) and (abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]) then
f[i]:=f[j];
inc(f[i]);
if f[i]>ans then ans:=f[i];
end;
assign(output,'mole.out'); rewrite(output);
writeln(ans);
close(output);
END.

三、最大连续子序列
给出一个长度为n 的整数序列A，找出i,j 使得那一段连续数之和最大。
第一行为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
read(a[i]);
s[i]:=s[i-1] + a[i];
end;
close(input);
for i:=1 to n do
for j:=1 to n do
if s[j] - s[i] > max then max := s[j] - s[i];
writeln(max);
end.

四、街道问题
在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。
[分析]
这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例子。通常，书上的解答是这样的：
按照图中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变量xk表示当前处于这一阶段上的哪一点。这时的模型实际上已经转化成了一个特殊的多段图。用决策变量uk=0表示向右走，uk=1表示向上走，则状态转移方程如下：
(这里的row是地图竖直方向的行数）
我们看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因而我们在实现时，一般是不会这么做的，而代之以下面方法：
（这里Distance表示相邻两点间的边长）
这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它的"状态转移"就不全是在两个阶段之间进行的了。
也许这没什么大不了的，因为实践比理论更有说服力。但是，如果我们把题目扩展一下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。这时，再用这种"简单"的方法就不太好办了。
如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径"不能重叠"的问题。
而我们回到原先"标准"的动态规划法，就会发现这个问题很好解决，只需要加一维状态变量就成了。即用xk=(ak,bk)分别表示两条路径走到阶段k时所处的位置，相应的，决策变量也增加一维，用uk=(xk,yk)分别表示两条路径的行走方向。状态转移时将两条路径分别考虑
在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策个数：
从这个例子可以看出，合理地划分阶段和选择状态可以给解题带来方便。

六、花店橱窗
假设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于架子上，并从1至V顺序编号，V是花瓶的数目，从左至右排列，则最左边的是花瓶1，最右边的是花瓶V。花束可以移动，并且每束花用1至F间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序，如果I＜J，则令花束I必须放在花束J左边的花瓶中。
例如，假设一束杜鹃花的标识数为1，一束秋海棠的标识数为2，一束康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。
每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。
在上述例子中，花瓶与花束的不同搭配所具有的美学值，如下表所示。
花 瓶
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中则显得十分难看。
为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果有不止一种的摆放方式具有最大的美学值，则其中任何一直摆放方式都可以接受，但你只要输出任意一种摆放方式。
（2）假设条件
1≤F≤100，其中F为花束的数量，花束编号从1至F。
F≤V≤100，其中V是花瓶的数量。
-50≤Aij≤50，其中Aij是花束i在花瓶j中的美学值。
（3）输入
第一行包含两个数：F，V。
随后的F行中，每行包含V个整数，Aij 即为输入文件中第（i+1 ）行中的第j个数。
（4）输出
一行是程序所产生摆放方式的美学值。
【样例输入1】 【样例输入2】
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

【样例输出1】 【样例输出2】
53

本题虽然是IOI’99中较为简单的一题，但其中大有文章可作。说它简单，是因为它有序，因此我们一眼便可看出这题应该用动态规划来解决。但是，如何动态规划呢？如何划分阶段，又如何选择状态呢？
<方法1>
以花束的编号来划分阶段。在这里，第k阶段布置第k束花，共有F束花，有F+1个阶段，增加第F+1阶段是为了计算的方便；状态变量xk表示第k束花所在的花瓶。而对于每一个状态xk，决策uk就是第k+1束花放置的花瓶号；最优指标函数fk(xk)表示从第k束花到第n束花所得到的最大美学值；A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F是花的总数。
状态转移方程为
规划方程为
边界条件为：
,
事实上这是一个虚拟的边界。
最后要求的最大美学价值是
<方法2>
方法1的规划方程中的允许决策空间：xk+1≤uk≤V-(F-k)+1 比较麻烦，因此有待改进。还是以花束的编号来划分阶段，第k阶段布置第k束花；状态变量xk表示第k束花所在的花瓶；注意，这里我们考虑倒过来布置花瓶，即从第F束花开始布置到第1束花。于是状态变量uk表示第k-1束花所在的花瓶；最优指标fk(xk)表示从第一束花到第k束花所获得的美学价值；A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F是花的总数。则状态转移方程为：
规划方程为：
增加的虚拟边界条件为：
最后要求的最大美学价值是：
可以看出，这种方法实质上和方法1没有区别，但是允许决策空间的表示变得简单了。
<方法3>
以花瓶的数目来划分阶段，第k个阶段决定花瓶k中是否放花；状态变量xk表示前k个花瓶中放了多少花；而对于任意一个状态xk，决策就是第xk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk(xk)表示前k个花瓶中插了xk束花，所能取得的最大美学值。注意，这里仍然是倒过来考虑。
状态转移方程为
规划方程为
边界条件为
三种不同的方法都成功地解决了问题，只不过因为阶段的划分不同，状态的表示不同，决策的选择有多有少，所以算法的时间复杂度也就不同。
这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别。所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。
七、航线设置
问题描述:美丽的莱茵河畔,每边都分布着N个城市,两边的城市都是唯一对应的友好城市,现需要在友好城市开通航线以加强往来.但因为莱茵河常年大雾,如果开设的航线发生交叉现象就有可能出现碰船的现象.现在要求近可能多地开通航线并且使航线不能相交!
假如你是一个才华横溢的设计师,该如何设置友好城市间的航线使的航线数又最大又不相交呢?
分析:此问题可以演化成求最大不下降序列来完成.源程序如下:
program dongtai; {动态规划之友好城市航线设置问题}
var
d:array[1..1000,1..4] of integer;
i,j,k,n,L,p:integer;
procedure print(L:integer); {打印结果}
begin
writeLn('最多可设置的航线数是 : ',k);
repeat
writeLn(d[L,1]:4,d[L,2]:4); {输出可以设置航线的友好城市代码}
L:=d[L,4]
untiL L=0
end;
begin
writeLn('输入友好城市对数: ');
readLn(n);
writeLn('输入友好城市对（友好城市放在同一行:'); {输入}
for i:=1 to n do
readLn(d[i,1],d[i,2]); {D[I，1]表示起点，D[I，2]表示终点}
for i:=1 to n do
begin
d[i,3]:=1; {D[I，3]表示可以设置的航线条数}
d[i,4]:=0 {D[I，4]表示后继，即下一条航线从哪里开始设置，为0表示不能设置下一条航线}
end;
for i:=n-1 downto 1 do {从倒数第二个城市开始规划}
begin
L:=0; p:=0; {L表示本城市后面可以设置的航线数，P表示下条航线从哪个城市开始}
for j:=i+1 to n do {找出本城市后面可以设置的最大航线数和小条航线到底从哪个城市开始设置}
if (d[i,2] L) then
{如果本城市I的终点小于后面城市的终点（即不相交）} {并且此城市后面可以设置的航线数大于L}
begin
L:=d[j,3]; {那么L等于城市J的可以设置航线数}
p:=j {P等于可以设置下条航线的城市代码}
end;
if L>0 then {如果本城市后面总共可以设置的航线数>0则}
begin
d[i,3]:=L+1; {本城市可以设置的航线数在下个城市可以设置航线数的基础上加1}
d[i,4]:=p {D[I，4]等于本城市后续城市的代码}
end
end;
k:=d[1,3]; {K为可以设置最大航线数，假设初值为第一个城市可以设置的航线数}
L:=1; {L为城市代码，初值为第一个城市}
for i:=2 to n do {找出可以设置航线的最大值，赋值给K，同时L记下哪个可以设置最大航线数的城市代码}
if d[i,3]>k then
begin
k:=d[i,3];
L:=i
end;
for i:=1 to n do {打印结果，因为有可能有多种方案，所以只要哪个城市可以设置的航线数等于最大值K就打印结果}
if d[i,3]=k then print(i)
end.
八、最长不降子序列
（1）问题描述
设有由n个不相同的整数组成的数列，记为:
a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)
例如3，18，7，14，10，12，23，41，16，24。
若存在i1<i2<i3< … < 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)则存在长度为2的不下降序列a(n-1)，a(n)。
②若a(n-1)>a(n)则存在长度为1的不下降序列a(n-1)或a(n)。
3· 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:
在a(i+1),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:array[1..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,a[i]);
b[n]:=1;
c[n]:=0;
end;
for i:= n-1 downto 1 do
begin
max:=0;p:=0;
for j:=i+1 to n do
if (a[i]<a[j]) and (b[j]>max) then begin max:=b[j];p:=j end;
if p<>0 then begin b[i]:=b[p]+1;c[i]:=p end
end;
max:=0;p:=0;
for i:=1 to n do
if b[i]>max then begin max:=b[i];p:=i end;
writeln('maxlong=',max);
write('result is:');
while p<>0 do
begin write(a[p]:5);p:=c[p] 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.若每种物品只有一件求旅行者能获得最大总价值。
<1>分析说明:
显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).
程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数
设 f(i，x)表示前i件物品，总重量不超过x的最优价值
则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））
f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;
动态规划方法(顺推法)程序如下:
程序如下：
program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;
for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.
使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。
3.完全背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
本问题的数学模型如下：
设 f(x)表示重量不超过x公斤的最大价值，
则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n
程序如下:（顺推法）
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do