动态规划初步.ppt

该【动态规划初步 】是由【我是药仙】上传分享，文档一共【41】页，该文档可以免费在线阅读，需要了解更多关于【动态规划初步 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。动态规划初步
动态规划简介
动态规划中有很多深奥的概念,使用动态规划也有很多前提条件,它与递推、递归也有着密切的联系,这些都要等到我们有一点编程经历后才好谈起,所以,我们先放开这些理论,不要被这些理论吓倒,而是去尝试分析和解决几个经典动态规划题目。
学****动态规划最重要的是“一种思想方法和解题过程”,请大家积极动脑动手,跟着我一起分析和体会其中的方法和过程,然后再独立去思考和实践。
常州市第一中学林厚从
动态规划简介
拦截导弹(NOIP1999)
问题描述:
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹的枚数和导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,每个数据之间有一个空格),计算这套系统最多能拦截多少导弹?如果要拦截所有导弹最少要配备多少套这种导弹拦截系统?
样例输入:
8
38920715530029917015865
样例输出:
6(最多能拦截的导弹数)
2(要拦截所有导弹最少要配备的系统数)
常州市第一中学林厚从
“拦截导弹”问题分析
先讨论第一问:假设a[i]表示拦截的最后一枚导弹是第i枚时,系统能拦得的最大导弹数。例如,样例中的a[5]=3,表示:如果系统拦截的最后一枚导弹是高度为299的话,最多可以拦截第1枚(389)、第4枚(300)、第5枚(299)三枚导弹。
显然,a[1]~a[8]中的最大值就是第一问的答案。关键是怎样求得a[1]~a[8]?
我们换一个角度,假设现在已经求得a[1]~a[7](注:在动态规划中,这样的假设往往是很必要的),那么怎样求a[8]呢?
a[8]要求系统拦截的最后1枚导弹必须是65,也就意味着倒数第2枚被拦截的导弹高度必须不小于65,则符合要求的导弹有389、207、155、300、299、170、158。
常州市第一中学林厚从
假如拦截的倒数第2枚导弹是300,则a[8]=a[4]+1;假如拦截的倒数第2枚导弹是299,则a[8]=a[5]+1;类似地,a[8]还可能是a[1]+1、a[2]+1、……。当然,我们现在要求得是以65结尾的最多导弹数目,因此a[8]要取所有可能值的最大值,即:a[8]=max{a[1]+1,a[2]+1,……,a[7]+1}
=max{a[i]}+1(i=1..7)。
类似地,我们可以假设a[1]~a[6]为已知,来求得a[7]。同样,a[6]、a[5]、a[4]、a[3]、a[2]也是类似求法,而a[1]就是1,即如果系统拦截的最后1枚导弹是389,则只能拦截第1枚。
“拦截导弹”问题分析
常州市第一中学林厚从
这样,求解过程可以用下列式子归纳:
a[1]=1
a[i]=max{a[j]}+1
其中:i>1,j=1..i-1,且h[j]>=h[i]
第一问的答案就是a[1]~a[8]中的最大值。
“拦截导弹”问题分析
常州市第一中学林厚从
longest[1]:=1;
fori:=2tondo{分阶段求出每步的最优值}
begin
maxlong:=1;
forj:=1toi-1do
ifh[i]<=h[j]then
iflongest[j]+1>maxlongthenmaxlong:=longest[j]+1;
longest[i]:=maxlong
end;
maxlong:=longest[1];{以下打擂台求出最大值}
fori:=2tondo
iflongest[i]>maxlongthenmaxlong:=longest[i];
writeln('max=',maxlong);
这种解题方法就称为“动态规划”
“拦截导弹”问题分析
常州市第一中学林厚从
“拦截导弹”问题分析
关于第二问:
由于它紧接着第一问,所以很容易受前面的影响,多次采用第一问的办法,然后得出总次数,其实这是不对的。要举反例并不难,比如长为7的高度序列“7541632”,最长不上升序列为“75432”,用多次求最长不上升序列的结果为3套系统;但其实只要2套,分别击落“7541”与“632”。所以不能用多次“动态规划”的方法做,那么,正确的做法又是什么呢?
我们的目标是用最少的系统击落所有导弹,至于系统之间怎么分配导弹数目则无关紧要,上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势,忽视了最优解中各个系统拦截数较为平均的情况,本质上是一种贪心算法,但贪心的策略不对。如果从每套系统拦截的导弹方面来想行不通的话,我们就应该换一个思路,从拦截某个导弹所选的系统入手。
常州市第一中学林厚从
“拦截导弹”问题分析
题目告诉我们,已有系统目前的瞄准高度必须不低于来犯导弹高度,所以,当已有的系统均无法拦截该导弹时,就不得不启用新系统。如果已有系统中有一个能拦截该导弹,我们是应该继续使用它,还是另起炉灶呢?事实是:无论用哪套系统,只要拦截了这枚导弹,那么系统的瞄准高度就等于导弹高度,这一点对旧的或新的系统都适用。而新系统能拦截的导弹高度最高,即新系统的性能优于任意一套已使用的系统。既然如此,我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹,究竟选哪一个呢?当前瞄准高度较高的系统的“潜力”较大,而瞄准高度较低的系统则不同,它能打下的导弹别的系统也能打下,它够不到的导弹却未必是别的系统所够不到的。所以,当有多个系统供选择时,要选瞄准高度最低的使用,当然瞄准高度同时也要大于等于来犯导弹高度。
常州市第一中学林厚从
“拦截导弹”问题分析
解题时用一个数组sys记下当前已有系统的各个当前瞄准高度,该数组中实际元素的个数就是第二问的解答。
sys[1]:=h[1];tail:=1;
fori:=2tondo
begin
minheight:=maxint;
forj:=1totaildo{找一套最适合的系统}
ifsys[j]>h[i]then
ifsys[j]<minheightthen
beginminheight:=sys[j];select:=jend;
ifminheight=maxint{开一套新系统}
thenbegintail:=tail+1;sys[tail]:=h[i]end
elsesys[select]:=h[i]
end;
writeln('total=',tail);
常州市第一中学林厚从