《ascal动态规划普及组》由会员分享，可在线阅读，更多相关《ascal动态规划普及组（17页珍藏版）》请在金锄头文库上搜索。
1、动态规划普及组三绍兴柯桥中学吴建锋.动态规划的应用问题5n n导弹拦截。某国为了防御敌国的导弹袭击，开展导弹拦截。某国为了防御敌国的导弹袭击，开展出一种导弹拦截系统。但是这种导弹拦截系统有出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。有可能不
2、能拦截所有的导弹。n n输入导弹依次飞来的高度雷达给出的高度输入导弹依次飞来的高度雷达给出的高度数据是不大于数据是不大于3000030000的正整数，计算这套系统的正整数，计算这套系统最多能拦截多少导弹？如果要拦截所有导弹最少最多能拦截多少导弹？如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？要配备多少套这种导弹拦截系统？.输入和输出n nmissile.inn n38920715530029917015865n nmissile.outn n6最多能拦截的导弹数n n2要拦截所有导弹最少要配备的系统数.顺推求解n n1、用fi表示从第1枚导弹到第i枚导弹这个子问题的最优解包含这枚导弹的决
3、策序列，aj表示第j枚导弹的高度。n n2、开始时所有的fi都初始化为1n n3、i从2开始直到n进行顺推计算所有的fin n4、最后输出最大的fi.某个阶段i的fi求解n n1、fi的子问题是哪些？n n2、fi子问题的最优解保存在哪里？n n3、如何根据子问题的最优解推算父问题的最优解？.状态转移方程n nFi=maxfj+1|必须满足的是所有的aj都必须不小于ai.核心程序段n nfillchar(f,sizeof(f),1);fillchar(f,sizeof(f),1);n nbest:=1;best:=1;n nfori:=2tondofori:=2tondon nbeginbeg
4、inn nforj:=1toi-1doforj:=1toi-1don nif(aj=ai)and(fj+1fi)thenif(aj=ai)and(fj+1fi)thenfi:=fj+1;fi:=fj+1;n nifbestfithenbest:=fi;ifbestfithenbest:=fi;n nend;end;n nwrite(best);write(best);.逆推求解n n如何进行？.问题6：乘积最大n n在一次数学智力竞赛中，主持人给所有参加活动的选手出了一在一次数学智力竞赛中，主持人给所有参加活动的选手出了一道题目：设有一个长度为道题目：设有一个长度为N N的数字串，要求选手使用
5、的数字串，要求选手使用MM个乘号个乘号将它分成将它分成MM1 1局部，求出一种分法，使得这局部，求出一种分法，使得这M+1M+1个局部的乘个局部的乘积最大。积最大。n n同时，为了帮助选手能够理解题意，主持人还举了如下一个同时，为了帮助选手能够理解题意，主持人还举了如下一个例子：例子：n n有一个数字串：有一个数字串：312312，当，当N=3,M=1N=3,M=1时有二种分法：时有二种分法：n n1 13123123636；n n2 23123126262n n这时，符合题意要求的结果是：这时，符合题意要求的结果是：3123126262。现在要求设计。现在要求设计一个程序，以求得正确的答案。
6、一个程序，以求得正确的答案。n n输入文件输入文件product.inproduct.in第一行包含二个整数，分别表示第一行包含二个整数，分别表示N N，MM2=N=102=N=10，1=M=51=M=5，第二行是一个长度为，第二行是一个长度为N N的数的数字串。字串。n n输出文件输出文件product.outproduct.out包含一行一个自然数，表示求得的最包含一行一个自然数，表示求得的最大乘积。大乘积。.输入和输出n nproduct.inn n42n n1231n nproduct.outn n62.算法分析n n1、本来用搜索也可n n2、n，m扩大时，必须用动态规划n n3、用
7、fI,j表示在前i个数字中插入j个乘号可以获得的最大值，那么fn,m就是问题的最优解。.特殊到一般抽象出转移方程n n1、显然fI,j这个最优解肯定是在以下情形中产生的：n nfj,j-1*Aj+1Ain nfj+1,j-1*Aj+2Ain nn nfi-1,j-1*Ai.n n2、提炼出初步的转移方程：n nfI,j=maxfi1,j-1*(ai1+1ai)|j=i1=i-1n n3、其中的(ai1+1ai)表示第i1+1位到第i位数字串所组成的整数。.勾画出初步的代码n nFori:=1tondon nForj:=0tomdon nIfj=i-1thenn nFori1:=jtoi-1don nIffI,jfi1,j-1*num(ai1+1ai);n n*开始时所有的fI,j初始化为0.思考n n1、有没有发现算法中的漏洞？n n2、分析边界、确定递推初始值中完善算法.完善后的算法n n所有的fI,j初始化为0；n nfori:=1ton-mdofI,0:=num(a1ai);n nFori:=2tondon nForj:=1tomdon nIfj=i-1thenn nFori1:=jtoi-1don nIffI,jfi1,j-1*num(ai1+1ai);.注意的细节n n实际编程时还须使用高精度算法，由于这里着重介绍动态规划，故本过程省略。.
