《动态规划初步》word版

《《动态规划初步》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、竞赛中，都至少有一道动态规划的题目。所以，掌握好动态规划，是非常重要的。动态规划是一种方法，是考虑问题的一种途径，而不是一种算法。因此，它不像深度优先和广度优先那样可以提供一套模式。它必须对具体问题进行具体分析。需要丰富的想象力和创造力去建立模型求解。[例8-1]拦截导弹某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可

3、能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUTOUTPUT389207155300299170158656（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）[问题分析]第一部分是要求输入数据串中的一个最长不上升序列的长度，可使用递推的方法，具体做法是从序列的第一个元素开始，依次求出以第i个元素为最后一个元素时的最长不上升序列的长度len(i)，递推公式为le

4、n(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”。那么，正确的做法又是什么呢？我们的目标是用最少的系统击落所有导弹，

5、至于系统之间怎么分配导弹数目则无关紧要；上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势，忽视了最优解中各个系统拦截数较为平均的情况，本质上是一种贪心算法。如果从每套系统拦截的导弹方面来想行不通的话，我们就应该换一个思路，从拦截某个导弹所选的系统入手。题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导弹高度，所以，当已有的系统均无法拦截该导弹时，就不得不启用新系统。如果已有系统中有一个能拦截该导弹，我们是应该继续使用它，还是另起炉灶呢？事实是：无论用哪套系统，只要拦截了这枚导弹，那么系统的瞄准高度就

6、等于导弹高度，这一点对旧的或新的系统都适用。而新系统能拦截的导弹高度最高，即新系统的性能优于任意一套已使用的系统。既然如此，我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹，究竟选哪一个呢？当前瞄准高度较高的系统的“潜力”10较大，而瞄准高度较低的系统则不同，它能打下的导弹别的系统也能打下，它够不到的导弹却未必是别的系统所够不到的。所以，当有多个系统供选择时，要选瞄准高度最低的使用，当然瞄准高度同时也要大于等于来犯导弹高度。解题时，用一个数组记下已有系统的当前瞄准高度，数据个数就是系统数目。[程序清

7、单]constmax=1000;vari,j,current,maxlong,minheight,select,tail,total:longint;height,longest,sys:array[1..max]oflongint;line:string;beginwrite('Inputtestdata:');readln(line);i:=1;whilei<=length(line)dobeginwhile(i<=length(line))and(line[i]='')doi:=i+1;current:=0

8、;while(i<=length(line))and(line[i]<>'')dobegincurrent:=current*10+ord(line[i])-ord('0');i:=i+1end;total:=total+1;height[total]:=currentend;longest[1]:=1;fori:=2tototaldobeginmaxlong:=1;fo