动态规划初步.doc

1 第八讲动态规划初步一、动态规划简介动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。 195 1 年,美国数学家贝尔曼( )提出了解决这类问题的“最优化原则”, 1957 年发表了他的名著《动态规划》,该书是动态规划方面的第一本著作。动态规划问世以来,在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用,取得了显著的效果。动态规划运用于信息学竞赛是在 90 年代初期,它以独特的优点获得了出题者的青睐。此后, 它就成为了信息学竞赛中必不可少的一个重要方法, 几乎在所有的国内和国际信息学竞赛中,都至少有一道动态规划的题目。所以,掌握好动态规划,是非常重要的。动态规划是一种方法, 是考虑问题的一种途径, 而不是一种算法。因此, 它不像深度优先和广度优先那样可以提供一套模式。它必须对具体问题进行具体分析。需要丰富的想象力和创造力去建立模型求解。[例 8-1] 拦截导弹某国为了防御敌国的导弹袭击, 发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷: 虽然它的第一发炮弹能够到达任意的高度, 但是以后每一发炮弹都不能高于前一发的高度。某天, 雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段, 所以只有一套系统, 因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数) ,计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例: INPUT OUTPUT 389 207 155 300 299 170 158 656 (最多能拦截的导弹数) 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”。那么,正确的做法又是什么呢? 我们的目标是用最少的系统击落所有导弹,至于系统之间怎么分配导弹数目则无关紧要; 上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势, 忽视了最优解中各个系统拦截数较为平均的情况, 本质上是一种贪心算法。如果从每套系统拦截的导弹方面来想行不通的话,我们就应该换一个思路,从拦截某个导弹所选的系统入手。题目告诉我们,已有系统目前的瞄准高度必须不低于来犯导弹高度,所以,当已有的系统均无法拦截该导弹时,就不得不启用新系统。如果已有系统中有一个能拦截该导弹,我们是应该继续使用它,还是另起炉灶呢?事实是:无论用哪套系统,只要拦截了这枚导弹, 那么系统的瞄准高度就等于导弹高度, 这一点对旧的或新的系统都适用。而新