动态规划初步

《动态规划初步》由会员分享，可在线阅读，更多相关《动态规划初步（14页珍藏版）》请在装配图网上搜索。

1、动态规划初步作者:日期:第八讲动态规划初步一、动态规划简介动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1 9 51年，美国数学家贝尔曼(R. Bellman)提出了解决这类问题的“最优化原则” 1957 年发表了他的名著动态规划该书是动态规划方面的第一本著作。动态规划问世以来， 在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用，取得了显著的效果。动态规划运用于信息学竞赛是在9 0年代初期，它以独特的优点获得了出题者的青睐。 此后，它就成为了信息学竞赛中必不可少的一个重要方法，几乎在所有的国内和国际信息学 竞赛中，都至少有一道动态规划的题目。所以，掌握好

2、动态规划，是非常重要的。动态规划是一种方法，是考虑问题的一种途径，而不是一种算法。因此，它不像深度优先 和广度优先那样可以提供一套模式。它必须对具体问题进行具体分析。需要丰富的想象力和 创造力去建立模型求解。例8-1 拦截导弹某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一 个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的 高度。某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统，因此 有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于30 0 00的正整数)，计算这套 系统最多能拦截多少

3、导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例：INPUT3 89 2071 55 3 0 0 2 9 91701 5 8 656 (最多能拦截的导弹数)2(要拦截所有导弹最少要配备的系统数)OUTPUTbb问题分析第一部分是要求输入数据串中的一个最长不上升序列的长度，可使用递推的方法，具体 做法是从序列的第一个元素开始，依次求出以第i个元素为最后一个元素时的最长不上升序 列的长度 len(i),递推公式为 l en (1)=1，l en(i)=ma x (le n (j )+ 1 )，其中 i1, j=1,2,i-1, 且j同时要满足条件:序列中第j个元素大于等于第i个元素

4、。第二部分比较有意思。由于它紧接着第一问,所以很容易受前面的影响，采取多次求最长 不上升序列的办法，然后得出总次数，其实这是不对的。要举反例并不难，比如长为7的高度 序列“ 7 5 4 1 6 3 2”，最长不上升序列为“7 5 4 3 2”，用多次求最长不上升序列的结 果为3套系统；但其实只要2套，分别击落“ 7 5 4 1”与“6 3 2 ”那么，正确的做法 又是什么呢？我们的目标是用最少的系统击落所有导弹，至于系统之间怎么分配导弹数目则无关紧 要；上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势，忽视了最优解中 各个系统拦截数较为平均的情况，本质上是一种贪心算法。如果从每套系

5、统拦截的导弹方面 来想行不通的话，我们就应该换一个思路,从拦截某个导弹所选的系统入手。题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导弹高度，所以，当已有的系 统均无法拦截该导弹时，就不得不启用新系统。如果已有系统中有一个能拦截该导弹，我们 是应该继续使用它，还是另起炉灶呢?事实是：无论用哪套系统，只要拦截了这枚导弹，那 么系统的瞄准高度就等于导弹高度，这一点对旧的或新的系统都适用。而新系统能拦截的导 弹高度最高，即新系统的性能优于任意一套已使用的系统。既然如此，我们当然应该选择已 有的系统。如果已有系统中有多个可以拦截该导弹，究竟选哪一个呢?当前瞄准高度较高的 系统的“潜力”较大，而瞄准

6、高度较低的系统则不同,它能打下的导弹别的系统也能打下，它够不到的导弹却未必是别的系统所够不到的。所以，当有多个系统供选择时,要选瞄准高度 最低的使用，当然瞄准高度同时也要大于等于来犯导弹高度。解题时，用一个数组记下已有系统的当前瞄准高度，数据个数就是系统数目。 程序清单c o nst max= 1 0 00;va r i ,j,c urr e n t, maxlong,m i nheight, s e lect,t ail, total:lon gi nt; height,】 ongest, sys:ar ray 1. max of Ion gi nt；li ne:string;beginw

7、r ite (I npu t test data:);readln( l ine)；i： =1;wh i le i=len g th (line) d obeg i nwhil e ( i =l e ngth(li n e ) and (linei= ) do i:=i+1; curr e n t:=0;while ( i ) do b egincurren t : = cur r ent*10+ o rd (l in e i)-ord(0);i： =i+1en d；tot a l：=t o ta l +1；h eightt o t a l:=cu r rentend;l o n gest1:

8、=1;for i:=2 to t o tal d obeginmax lo n g := 1；for j： = 1 to i1 dob e g inif h e ig h t imax longt h en ma x long:=lo n ge s t j +1； lon ge st i :=maxl ongend;end；maxlon g:=lo n ge s t1;for i:=2 to to tal d oi f l on g e s t imax long t h en maxl o ng:=lon g es t i； wr i teln (m a xlon g)；sys1 :=he

9、i ght 1; tai l : = 1 ；for i:=2 to total dobeg inminheight:=maxi n t;for j :=l*to t ail doi f sysj heigh t i th e n if sysj=10 t h enbeginai+ 1 :=ai+ 1+1;ai:=a i -10endend;proc e dur e pr i nt(a:arrayty p e);var i， j： lo n gin t ;begini:=maxlen;while (i0) and (a i=0) d o i: = i-1;for j:=i down to Odo

10、 wri t e(a j)end;be g inwrite (z Inpu t n:); read ln(n);fori:=1 to ma xlendo totali：=0 ；tot al0:=1;fori: = 1 to nldoadd(to t al,t otal);f ori: = 1 to maxndof or j:=1 tomaxndofor k:=0 to maxlen do fi,j,k： = 0 ;for i:=1 to max n d o fi,l,0: = l；for i： =1 to maxn do fi,i,0: = l;for nn:=2 to n dofor k:=

11、2 to nn-1 dobegi nfor i:=1 to k-1 do add(fnn, k,fnni, k);f or i： =1 to k doi f nn-k=i t hen add (fnn,k,f nn-k, i)end;wri t e(Tot al = );pri nt(tot al);writeln;for k： =1 to n dob e ginwrite( Height = ,k:2,Kind二：10);print(fn, k)； write 1 n;if k mod 2 3 = 0t h enbegi nwrite (PressEn terto contin ue! );

12、readlnen de nd;writ e(PressEnt er to contin ue!)；readlnend.例8-3投资问题：有n万元的资金，可投资于m个项目，其中m 和n为小于100的自然数。对第i (1 WiWm)个项目投资j万元(1WjWn,且j为整数)可获得的回报为Q (i , j),请编程序，求 解并输出最佳的投资方案(即获得回报总值最高的投资方案)。输入数据放在一个文本文件中，格式如下：m nQ(1,0) Q(1 , 1)Q(1, n)Q(2 ,0)Q(2 , 1)Q(2 , n)Q(m , 0) Q(叩,1)Q(m , n)输出数据格式为：r(1) r(2) r(m)

13、P其中r(i) (lWiWm )表示对第i个项目的投资万元数，P为总的投资回报值，保留两 位有效数字，任意两个数之间空一格。当存在多个并列的最佳投资方案时，只要求输出其中 之一即可。如输入数据如下时：2 301.11.31 .90 2.12.52.6屏幕应输出：12 3.6问题分析本题可供考虑的递推角度只有资金和项目两个角度，从项目的角度出发，逐个项 目地增加可以看出只要算出了对前k个项目投资j万元最大投资回报值(1WjWn),就能推出 增加第k+1个项目后对前k+1个项目投资j万元最大投资回报值(1WjWn),设Pk,j为前k 个项目投资j万元最大投资回报值，则Pk+1,j= Max(Pk,

14、i+Qk+1,ji),0v=i V=j,k= 1时，对第一个项目投资j万元最大投资回报值(0WjWn)是已知的(边界条件)。 算法设计动态规划的时间复杂度相对于搜索算法是大大降低了，却使空间消耗增加了很 多。所以在设计动态规划的时候，需要尽可能节省空间的占用。本题中如果用二维数组存储 原始数据和最大投资回报值的话，将造成空间不够，事实上，从前面的问题分析可知：在计 算对前k+1个项目投资j万元最大投资回报值时，只要用到矩阵Q的第k+1行数据和对前 k个项目投资j万元最大投资回报值，而与前面的数据无关，后者也只需有一个一维数组存 储即可，程序中用一维数组Q存储当前项目的投资回报值，用一维数组ma

15、 xreturn存储对 当前项目之前的所有项目投资j万元最大投资回报值(OWjWn)，用一维数组temp存储对 到当前项目为止的所有项目投资j万元最大投资回报值(0WjWn)。为了输出投资方案，程序 中使用了一个二维数组i n v e s t, in ve s tk,j记录了对前k个项目投资j万元获得最大 投资回报时投资在第k个项目上的资金数。程序清单pro gram ex8_3(input,outpu t ); const maxm=100； max n=1 0 0;type arra ytyp e=ar ray 0.maxn of real；var i， j, k，m, n , r es

16、t:int e ger;q,maxre turn, t emp：arra yty p e;inv es t: array 1.maxm,0. .maxn of inte ger;res ult:a rrayl.maxm of i nte ger；f name:s t ring;f:text;begi nwrit e(Inp ut the name of dat a file：);readln (fname);a s sig n (f,fname);re set(f);re a dln (f,m， n)；for j:=0 to n d o read(f,qj);readln(f)；fo r i:

17、 =1 to m dofor j:=0 to n d o inves ti,j:=O;maxre t urn: = q;for j： =0 to n do inv est 1, j : = j；fo r k：=2 to m dobegintemp：=ma xre turn;for j:=0 to n do invest k, j:=0;for j :=0 to n do read(f,qj);re adln(f)；f or j:=0 to n dofor i:=0 to j doif max re turn j-i+qi t empj t henbegintem pj:=maxr eturn

18、j-i+q i;i n ves t k,j: =ien d；maxr e tu rn：二t empen d；close(f);res t : =n；for i：=m down to 1 dobeginresu lti：二inves ti ,res t;res t:= res t res ult iend;for i:=1 to m d o write (resu lti,);write l n(max r eturnn:0:2)end.例8-4花店橱窗布置问题(FLOWER)(1) 问题描述假设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也 有至少同样数量的花瓶被按顺序

19、摆成一行。这些花瓶的位置固定于架子上并从1至V顺序 编号,V是花瓶的数目，从左至右排列则最左边的是花瓶1,最右边的是花瓶V。花束可以移 动,并且每束花用1至F间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序， 如果I VJ,则令花束I必须放在花束J左边的花瓶中。例如，假设一束杜鹃花的标识数为1, 一束秋海棠的标识数为2, 束康乃馨的标识数 为3,所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边 的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余 的花瓶必须空置，且每个花瓶中只能放一束花。每一个花瓶都具有各自的特点。因此，当各个花瓶

20、中放入不同的花束时，会产生不同的 美学效果，并以美学值(一个整数)来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，如下表所示。花 瓶12345花束1 （杜鹃花）7235-241 62 （秋海棠）521-410233 （康乃馨）-215-4-2020例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看;但若放在花瓶4中则显得十 分难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学 值。如果有不止一种的摆放方式具有最大的美学值，则其中任何一直摆放方式都可以接受， 但你只要输出任意一种摆放方式。（2）假设条件 1WFW100，其中F为花束

21、的数量，花束编号从1至F。 FWVW10 0,其中V是花瓶的数量。 -50WA W50，其中A是花束i在花瓶j中的美学值。1 jij（3）输入输入文件是正文文件（t ex t file），文件名是flower.inp。第一行包含两个数:F,V。随后的F行中，每行包含V个整数，A 即为输入文件中第（i + 1 ）行中的第jij个数。（4）输出输出文件必须是名为flower. out的正文文件，文件应包含两行：第一行是程序所产生摆放方式的美学值。第二行必须用F个数表示摆放方式，即该行的第K个数表示花束K所在的花瓶的编号。例子f lower.inp:3 57 23 -5 -24 165 21 -4

22、10 2321 5 4 20 20f lo wer. out:532 4 5(6)评分程序必须在2秒中内运行完毕。在每个测试点中，完全正确者才能得分。算法设计flower 一题是I OI 9 9第一天第一题，该题如用组合的方法处理，将会造成超时。 正确的方法是用动态规划，考虑角度为一束一束地增加花束，假设用b(i,j)表示1i束花 放在1至1打之间的花瓶中的最大美学值，其中i0 t h enbe gini := c urren t ;w h ile v al c u rre nt, i ma x_val d o i：=i +1;pr int(curren t -1 ,max_ va l-tab

23、lecurre n t,i)；w r it e (i，)endend；beginw r ite(I n pu t the o f test data:);readln (fn ame);a ssi g n(fin， f name);r e set (f in);r ea dln (f i n,f,v);for i: = 1 to f dobeginf or j:=1 to v d o read(f in， tab 1 e i , j );readln(fin);en d ;c lo se( fi n);m a x_val:=-m a xint;for i :=1 to v doif max_v

24、a l cm a x th e n cmax： ble i ,curr ent；if cm a x+v a li 1,k ma x _va l then max _va l : x+v al i-1 , k e nd;v ali,j :=max_valend;m a x_val:=-max in t;for i:=f to v doif valf, i max_val t hen max_va l := v alf,i;w r iteln (max_val)；pr i nt (f,max_val)；writ e lnend.运彳丁结果参见flower子目录下的标准答案和测试数据。3 57 2 3524165金2 1 -4 10 23521-420 2 0a532 4 5