动态规划练习试题和解答

5/5动态规划练习试题和解答动态规划练习题

[题1]多米诺骨牌（DOMINO）

问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。

现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。

输入格式：

文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。

输出格式：

只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。

[题2]Perform巡回演出

题目描述:

Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出).

由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.

输入:输入文件包括若干个场景.每个场景的描述由一对整数n(20theninc(t[1]^[x]);

end;

end;

ifm=0then

begin

writeln(f2,0);

close(f2);

halt;

end;

{处理步数为零的情况}

l[1]:=m;

f[m]:=1;

end;

proceduremain;

{主过程}

begin

repeat

forft:=ft+1toredo

{以步数为阶段扩展状态}

begin

x:=l[ft];

fori:=1to6do

{不同差值的六种情况}

begin

ifx-6then

if(t[ft]^[i]>0)and(f[x-i*2]=0)then

begin

inc(re);l[re]:=x-i*2;

f[l[re]]:=f[x]+1;

ifl[re]=0then

{找到解便打印}

begin

writeln(f2,f[l[re]]-1);

close(f2);

halt;

end;

new(t[re]);

t[re]^:=t[ft]^;

dec(t[re]^[i]);

end;

{差值减少}

end;

end;

untilft=re;

fori:=1to6do

if(f[i]>0)or(f[-i]>0)then

begin

if(f[-i]>0)and((f[i]=0)or(f[-i]0)},动态规划方程一出,尽可以放怀大笑了.

示范程序:

programperform_hh;

var

f,fout:text;

p,l,i,j,n,k:integer;

a:array[1..1000,1..10]ofinteger;{动态规划数组}

c:array[1..10,1..10]ofrecord{航班价格数组}

num:integer;

t:array[1..30]ofinteger;

end;

e:array[1..1000]ofinteger;

procedurework;

begin

{人工赋第一天各城市最优值}

fori:=1tondo

begin

ifc[1,i].t[1]l)

and(c[l,j].t[(i-1)modc[l,j].num+1]0)and(k0)do

begin

p:=p+1;

fillchar(c,sizeof(c),0);

fillchar(a,sizeof(a),0);

fori:=1tondo

begin

forj:=1toi-1do

begin

read(f,c[i,j].num);

forl:=1toc[i,j].numdo

read(f,c[i,j].t[l]);

end;

forj:=i+1tondo

begin

read(f,c[i,j].num);

forl:=1toc[i,j].numdo

read(f,c[i,j].t[l]);

end;

end;

work;

readln(f,n,k);

end;

{输出各个场景的解}

fori:=1top-1do

writeln(fout,e[i]);

write(fout,e[p]);

close(f);

close(fout);

end;

begin

readfile;

end.

[题3：]

解决问题：该题中M本书是顺序排列的，K个抄写员选择数也是顺序且连续的。不管以书的编号，还是以抄写员标号作为参变量划分阶段，都符合策略的最优化原理和无后效性。考虑到K〈=M，以抄写员编号来划分会方便些。

设F（I，J）为前I个抄写员复制前J本书的最小“页数最大数”。于是便有F（I，J）=MIN{F（I-1，V），T（V+1，J）}（1〈=I〈=K，I〈=J〈=M-K+I，I-1〈=V〈=J-1〉。其中T（V+1，J）表示从第V+1本书到第J本书的页数和。起步时F（1，1）=P1。

观察函数递推式，发现F（I）阶段只依赖于F（I-1）阶段的状态值，编程时可令数组F的范围为（0…1,1…M），便于缩小空间复杂度。

程序如下：

programbooks;

typetp=array[1..500]ofinteger;

tc=array[1..500]oflongint;

varc:array[1..500]of^tp;

{记录路径}

f:array[0..1]oftc;

{状态值}

t:tc;

{书本页数和}

cc:tp;

{链接路径}

i,j,v,k,m,x,y,min,p1,p2:longint;

f1,f2:text;

procedureinit;

{输入部分}

begin

assign(f1,'books.dat');

reset(f1);

assign(f2,'books.out');

rewrite(f2);

readln(f1,m,k);

ifk=1then

begin

writeln(f2,1,'',m);

close(f2);

halt;

end;

{当k=1时,作特殊处理}

fori:=1tomdo

begin

read(f1,j);

ifi=1thent[1]:=jelse

t[i]:=t[i-1]+j;

{累加页数}

end;

fori:=1tokdo

new(c[i]);

end;

proceduremain;

{主过程}

begin

p1:=1;f[1]:=t;

{起步状态}

fori:=2tok-1do

{利用函数递推式计算}

begin

p2:=p1;p1:=1-p2;

forj:=itom-k+ido

begin

min:=maxlongint;y:=0;

forv:=i-1toj-1do

begin

iff[p2,v]>t[j]-t[v]thenx:=f[p2,v]elsex:=t[j]-t[v];ifxt[m]-t[i]thenx:=f[p2,i]elsex:=t[m]-t[i];

ifx<minthenbeginmin:=x;y:=i;end;

end;

{最后找出最优分配方案}

fori:=k-1downto1do

begin

cc[i]:=y;

y:=c[i]^[y];