动态规划初步.doc

螄第八讲动态规划初步袃一、动态规划简介***动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年,美国数学家贝尔曼()提出了解决这类问题的“最优化原则”,1957年发表了他的名著《动态规划》,该书是动态规划方面的第一本著作。动态规划问世以来,在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用,取得了显著的效果。羆动态规划运用于信息学竞赛是在90年代初期,它以独特的优点获得了出题者的青睐。此后,它就成为了信息学竞赛中必不可少的一个重要方法,几乎在所有的国内和国际信息学竞赛中,都至少有一道动态规划的题目。所以,掌握好动态规划,是非常重要的。膅动态规划是一种方法,是考虑问题的一种途径,而不是一种算法。因此,它不像深度优先和广度优先那样可以提供一套模式。它必须对具体问题进行具体分析。需要丰富的想象力和创造力去建立模型求解。芀[例8-1]拦截导弹膀 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。羆 输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。节样例:肂INPUTOUTPUT羈389207155300299170158656(最多能拦截的导弹数)肆 2(要拦截所有导弹最少要配备的系统数)蚂[问题分析]蒀第一部分是要求输入数据串中的一个最长不上升序列的长度,可使用递推的方法,具体做法是从序列的第一个元素开始,依次求出以第i个元素为最后一个元素时的最长不上升序列的长度len(i),递推公式为len(1)=1,len(i)=max(len(j)+1),其中i>1,j=1,2,…i-1,且j同时要满足条件:序列中第j个元素大于等于第i个元素。螇第二部分比较有意思。由于它紧接着第一问,所以很容易受前面的影响,采取多次求最长不上升序列的办法,然后得出总次数,其实这是不对的。要举反例并不难,比如长为7的高度序列“7541632”,最长不上升序列为“75432”,用多次求最长不上升序列的结果为3套系统;但其实只要2套,分别击落“7541”与“632”。那么,正确的做法又是什么呢?膆我们的目标是用最少的系统击落所有导弹,至于系统之间怎么分配导弹数目则无关紧要;上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势,忽视了最优解中各个系统拦截数较为平均的情况,本质上是一种贪心算法。如果从每套系统拦截的导弹方面来想行不通的话,我们就应该换一个思路,从拦截某个导弹所选的系统入手。肃题目告诉我们,已有系统目前的瞄准高度必须不低于来犯导弹高度,所以,当已有的系统均无法拦截该导弹时,就不得不启用新系统。如果已有系统中有一个能拦截该导弹,我们是应该继续使用它,还是另起炉灶呢?事实是:无论用哪套系统,只要拦截了这枚导弹,那么系统的瞄准高度就等于导弹高度,这一点对旧的或新的系统都适用。而新系统能拦截的导弹高度最高,即新系统的性能优于任意一套已使用的系统。既然如此,我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹,究竟选哪一个呢?当前瞄准高度较高的系统的“潜力”较大,而瞄准高度较低的系统则不同,它能打下的导弹别的系统也能打下,它够不到的导弹却未必是别的系统所够不到的。所以,当有多个系统供选择时,要选瞄准高度最低的使用,当然瞄准高度同时也要大于等于来犯导弹高度。膂解题时,用一个数组记下已有系统的当前瞄准高度,数据个数就是系统数目。螀[程序清单]芆constmax=1000;蒄vari,j,current,maxlong,minheight,select,tail,total:longint;蚀height,longest,sys:array[1..max]oflongint;蕿line:string;莅begin羅write('Inputtestdata:');莂readln(line);莈i:=1;蒅whilei<=length(line)do肂begin袀while(i<=length(line))and(line[i]='')doi:=i+1;肇current:=0;薅while(i<=length(line))and(line[i]<>'')do蒃begin肀current:=current*10+ord(line[i])-ord('0');蚈i:=i+1膃end;莂total:=total+1;薈height[total]:=current蒇end;芃longest