动态规划练习试题和解答

1、动态规划练习题题1多米诺骨牌(DOMINO)问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。输入格式：文件的第一行是一个整数n(1=n=1000，表示有n个多米

2、诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b(0=a、b=6，中间用空格分开。第1+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数(0表示空)。输出格式：只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。题2Perform巡回演出题目描述:Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的，乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一城市，最后才到达目的地Harp市(乐团可多次

3、在同一城市演出).由于航线的费用和班次每天都在变，城市和城市之间都有一份循环的航班表，每一时间，每一方向，航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.输入：输入文件包括若干个场景.每个场景的描述由一对整数n(2v=nv=10)和k(lv=kv=1000)开始，音乐家们要在这n个城市作巡回演出,城市用1.n标号，其中1是起点Flute市,n是终点Harp市，接下来有n*(n-1)份航班表，一份航班表一行，描述每对城市之间的航线和价格，第一组n-1份航班表对应从城市1到其他城市(2,3，.n)的航班，接下的n-1行是从城市2到其他城市(1,3,4.n)的航班，如此下去.每份航班

4、又一个整数d(1v=dv=3O)开始，表示航班表循环的周期，接下来的d个非负整数表示1，2.d天对应的两个城市的航班的价格，价格为零表示那天两个城市之间没有航班.例如"375080"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班，如此循环.输入文件由n=k=0的场景结束.输出:对每个场景如果乐团可能从城市1出发，每天都要飞往另一个城市，最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线，输出0.样例输入:样例输出：WORD格式专业整理362130150375

5、0807120110010011012004607060503013514027080232070180004600题3复制书稿（BOOKS）问题描述：假设有M本书（编号为1,2,M）,想将每本复制一份，M本书的页数可能不同（分别是Pl,P2,PM）。任务时将这M本书分给K个抄写员（K二M，每本书只能分配给一个抄写员进行复制，而每个抄写员所分配到的书必须是连续顺序的。意思是说，存在一连续升序数列0=boblb2<bk-1<bk=m，这样，第I号抄写员得到的书稿是从bi-1+l到第bi本书。复制工作是同时开始进行的,并且每个抄写员复制的速度都是一样的。所以，复制完所有书稿所需时间取决

6、于分配得到最多工作的那个抄写员的复制时间。试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小（如存在多个最优方案，只输出其中一种）。输入格式：文件的第一行是两个整数m和k（1二k二m=500）。第二行有m个整数Pl,P2，P叫这m个整数均为正整数且都不超过1000000。每两个整数之间用空格分开。输出格式：文件有k行，每行有两个正整数。整数之间用空格分开。第I行的两个整数ai和bi,表示第I号抄写员所分配得到的书稿的起始编号与终止编号。WORD格式专业整理动态规划题参考程序：题1：解决问题：例子的上下部分之差是6+1+1+1-(1+5+3+2)=(6-1)+(1-5)+(1-3)

7、+(1-2)=-2，而翻转最后一个骨牌后，上下之差变为(6-1)+(1-5)+(1-3)+(2-1)=0。由此看出，一个骨牌对翻转策略造成影响的是上下两数之差，骨牌上的数则是次要的了。这么一来，便把骨牌的放置状态由8个数字变为4个：5-4-2-1，翻转时只需取该位数字的相反数就行了。在本题中，因为各骨牌的翻转顺序没有限定，所以不能按骨牌编号作为阶段来划分。怎么办呢？考虑到隐含阶段类型的问题可以按状态最优值的大小来划分阶段。于是，我们以骨牌序列上下两部分的差值I作为状态，把达到这一状态的翻转步数作为状态值，记为f(I)。便有f(I)=minf(I+j)+1(-12二j<=12,j为偶数，且

8、要求当前状态有差值为j/2的骨牌)。这里，I不是无限增大或减小，其范围取决于初始骨牌序列的数字差的和的大小。具体动态规划时，如例题，我们以f(-2)=0起步，根据骨牌状态，进行一次翻转，可得到f(-12)=1，f(6)=1，f(2)=1，f(0)=1，由于出现了f(0)，因此程序便可以结束，否则将根据四个新状态继续扩展，直至出现f(0)或者无法生成新状态为止。注意：在各状态，除记录最少步数外，还需记录到达这一状态时各骨牌的放置情况；而当到达某一状态发现已记录有一种翻转策略时，则取步数较小的一种。程序如下：programdomino;typetp=array1.6ofinteger;vart:a

9、rray1.6000of"tp;记录骨牌摆放状态f:array-6000.6000ofinteger;记录达到某个差值的最少步数l:array1.6000ofinteger;扩展队列tt:tp;i,j,n,m,x,y,ft,re:integer;f1,f2:text;procedureinit;程序初始化beginassign(f1,'domino.dat');reset(f1);assign(f2,'domino.out');rewrite(f2);m:=0;ft:=0;re:=1;new(t1);fillchar(t1",sizeof(t

10、1"),0);fillchar(f,sizeof(f),0);fillchar(tt,sizeof(tt),0);readln(f1,n);fori:=1tondobeginreadln(f1,x,y);ifx<>ythenbeginx:=x-y;inc(m,x);inc(ttabs(x);ifx0theninc(tl"x);end;end;ifm=0thenbeginwriteln(f2,0);close(f2);halt;end;处理步数为零的情况l1:=m;fm:=1;end;proceduremain;主过程beginrepeatforft:=ft+1t

11、oredo以步数为阶段扩展状态beginx:=lft;fori:=1to6do不同差值的六种情况beginifx<6then辻(tft"itti)and(fx+i*2=0)thenbegininc(re);lre:=x+i*2;flre:=fx+1;iflre=0then找到解便打印beginwriteln(f2,flre-1);close(f2);halt;end;new(tre);tre:二tft；inc(trei);end;差值增加ifx-6then辻(tft"i0)and(fx-i*2=0)thenbegininc(re);lre:=x-i*2;flre:=f

12、x+1;iflre=0then找到解便打印beginwriteln(f2,flre-1);close(f2);halt;end;new(tre);tre:二tft；dec(trei);end;差值减少end;end;untilft=re;fori:=1to6doif(fi>0)or(f-i>0)thenbeginif(f-i>0)and(fi=0)or(f-i<fi)thenx:=f-ielsex:=fi;writeln(f2,x-1);i:=6;end;close(f2);骨牌上下两行点数之和的绝对值不为零end;begininit;main;end.题2：初看这道题

13、，很容易便可以想到动态规划,因为第x天在第y个地方的最优值只与第x-1天有关,符合动态规划的无后效性原则,即只与上一个状态相关联,而某一天x航班价格不难求出S=C(x-1)modm+1.我们用天数和地点来规划用一个数组A1.1OOO,1.1O来存储,Ai,j表示第i天到达第j个城市的最优值,Ci,j,l表示i城市与j城市间第l天航班价格,则Ai,j=MinAi-1,l+Cl,j,i(l=1.n且Cl,j,iv>0),动态规划方程一出,尽可以放怀大笑了.示范程序:programperform_hh;varf,fout:text;p,l,i,j,n,k:integer;a:array1.10

14、00,1.10ofinteger;动态规划数组c:array1.10,1.10ofrecord航班价格数组num:integer;t:array1.30ofinteger;end;e:array1.1000ofinteger;procedurework;begin人工赋第一天各城市最优值fori:=1tondobeginifc1,i.t1<>0thena1,i:=c1,i.t1;end;fori:=2tokdobeginforj:=1tondobeginforl:=1tondobeginif(j<>l)and(cl,j.t(i-1)modcl,j.num+1<&g

15、t;0)判断存在航班and(ai,j=0)or(ai-1,l+cl,j.t(i-1)modcl,j.num+1<ai,j)判断比当前解优thenai,j:=ai-1,l+cl,j.t(i-1)modcl,j.num+1;赋值end;end;end;ep:=ak,n;第p个场景的最优值end;procedurereadfile;读文件beginassign(f,'PERFORM.DAT');reset(f);assign(fout,'PERFORM.OUT');rewrite(fout);readln(f,n,k);p:=0;while(n<>0

16、)and(k<>0)dobeginp:=p+1;fillchar(c,sizeof(c),0);fillchar(a,sizeof(a),0);fori:=1tondobeginforj:=1toi-1dobeginread(f,ci,j.num);forl:=1toci,j.numdoread(f,ci,j.tl);end;forj:=i+1tondobeginread(f,ci,j.num);forl:=1toci,j.numdoread(f,ci,j.tl);end;end;work;readln(f,n,k);end;输出各个场景的解fori:=1top-1dowritel

17、n(fout,ei);write(fout,ep);close(f);close(fout);end;beginreadfile;end.题3：解决问题：该题中M本书是顺序排列的，K个抄写员选择数也是顺序且连续的。不管以书的编号，还是以抄写员标号作为参变量划分阶段，都符合策略的最优化原理和无后效性。考虑到K=M，以抄写员编号来划分会方便些。设F(I,J)为前I个抄写员复制前J本书的最小“页数最大数”于是便有F(I，J)=MINF(I-1，V)，T(V+1，J)(1=I=K，I=J=M-K+I，I-1二V=J-1。其中T(V+l,J)表示从第V+1本书到第J本书的页数和。起步时F(1，1)=P1

18、。观察函数递推式，发现F(I)阶段只依赖于F(I-1)阶段的状态值，编程时可令数组F的范围为(01,1M),便于缩小空间复杂度。程序如下：programbooks;typetp=array1.500ofinteger;tc=array1.500oflongint;varc:array1.500of"tp;记录路径f:array0.1oftc;状态值t:tc;书本页数和cc:tp;链接路径i,j,v,k,m,x,y,min,p1,p2:longint;f1,f2:text;procedureinit;输入部分beginassign(f1,'books.dat');reset(f1);assign(f2,'books.out');rewrite(f2);readln(f1,m,k);ifk=1thenbeginwriteln(f2,1,'',m);close(f2);halt;end;当k=1时,作特殊处理fori:=1tomdobeginread(f1,j);ifi=1thent1:=jelseti:=ti-1+j;累加页数en