ascal动态规划普及组

《ascal动态规划普及组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划（普及组）三绍兴柯桥中学吴建锋动态规划的应用（问题5）导弹拦截。某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹？如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？输入和输出missile.in38920715530029917015865missile.out6（最

2、多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）顺推求解1、用f[i]表示从第1枚导弹到第i枚导弹这个子问题的最优解（包含这枚导弹的决策序列），a[j]表示第j枚导弹的高度。2、开始时所有的f[i]都初始化为13、i从2开始直到n进行顺推计算所有的f[i]4、最后输出最大的f[i]某个阶段i的f[i]求解1、f[i]的子问题是哪些？2、f[i]子问题的最优解保存在哪里？3、如何根据子问题的最优解推算父问题的最优解？状态转移方程F[i]=max{f[j]+1

3、必须满足的是所有的a[j]都必须不小于a[i]}核心程序段fillchar(f,sizeof(f),1);best:=1;fori

4、:=2tondobeginforj:=1toi-1doif(a[j]>=a[i])and(f[j]+1>f[i])thenf[i]:=f[j]+1;ifbest

5、题意要求的结果是：31×2＝62。现在要求设计一个程序，以求得正确的答案。输入文件product.in第一行包含二个整数，分别表示N，M（2<=N<=10，1<=M<=5），第二行是一个长度为N的数字串。输出文件product.out包含一行一个自然数，表示求得的最大乘积。输入和输出product.in421231product.out62算法分析1、本来用搜索也可2、n，m扩大时，必须用动态规划3、用f[I,j]表示在前i个数字中插入j个乘号可以获得的最大值，那么f[n,m]就是问题的最优解。特殊到一般抽象出转移方程1、显然f[I,j]这个最优解肯定是在下列情形中产生的：f[j,j-1]*A

6、j+1…Aif[j+1,j-1]*Aj+2…Ai……f[i-1,j-1]*Ai2、提炼出初步的转移方程：f[I,j]=max{f[i1,j-1]*(a[i1+1]…a[i])

7、j<=i1<=i-1}3、其中的(a[i1+1]…a[i])表示第i1+1位到第i位数字串所组成的整数。勾画出初步的代码Fori:=1tondoForj:=0tomdoIfj<=i-1thenFori1:=jtoi-1doIff[I,j]

8、I,j]初始化为0；fori:=1ton-mdof[I,0]:=num(a[1]…a[i]);Fori:=2tondoForj:=1tomdoIfj<=i-1thenFori1:=jtoi-1doIff[I,j]