动态规划问题———拦截导弹(C语言)

  • 时间:
  • 浏览:
  • 来源:互联网

6.拦截导弹
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,由于该系统还在试用阶段。所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度不大于30000的正整数)。计算这套系统最多能拦截多少导弹。

输入:N颗依次飞来的导弹高度,(导弹个数大于1000)。
输出:一套系统最多拦截的导弹数,并依次打印输出被拦截导弹的高度。

该问题可近似等效为求不连续的最长递减子序列
把导弹编号为1~N
建立数组a[N+1]储存每枚导弹的高度 //a[0] ~a[N]
为便于理解从a[1]开始启用 ,下同
建立数组dp[N+1]储存拦截的数量
dp[i]表示前i枚拦截的最大数量

int i,j,m,n=1,Max=1;	//m储存当取最大拦截数量时dp数组的系数 
	int a[N+1]={0};		//储存每枚导弹的高度 
	int dp[N+1]	;			//dp[i]表示从1到第i枚最大拦截数量 
							//N+1表示数组的大小 从dp[0]~dp[N]共N+1个

问题所求最大拦截数dp[N]可划分为子问题dp[N-1]以及a[N]和a[N-1]的大小有关

if(a[N]<a[N-1])
	dp[i]=max(dp[N],dp[N-1]+1)

dp[i]=max(dp[N],dp[N-1]+1)即为该问题的状态方程

if(a[i]<a[j])		//后一枚高度低于前一枚   
			dp[i]=max(dp[i],dp[j]+1);	//当前拦截的最大数量与前面最大数量+1比较 取大的 

因为第一发可以拦截任意高度的导弹,所以dp[i]=1
即最少可以拦截本身

for(i=1;i<N+1;i++)		
	{
		dp[i]=1;	//拦截导弹数量的初值为1  即最少可以拦截本身 
	}

则i从1~N依次求dp[i]

for(i=1;i<N+1;i++)
	{
		for(j=1;j<i;j++)	//遍历i前面的 
		{
			if(a[i]<a[j])		//后一枚高度低于前一枚   
			dp[i]=max(dp[i],dp[j]+1);	//当前拦截的最大数量与前面最大数量+1比较 取大的 
		}
	}

最后比较dp数组得出最大值

	for(i=1;i<N+1;i++)		//取最大拦截数量 
	{
		Max=max(Max,dp[i]);
		if(dp[i]==Max)
		m=i; 			//m储存当取最大拦截数量时dp数组的系数 
	}

要求依次打印拦截的高度
则取dp数组与最大值进行比较
相同时则记录拦截高度
同时Max减1,记录数组的标号+1
因为第m个已经比较完
则继续比较m-1个
直到比较完第一个
此时m=0退出循环

while(m)		
	{
		if(dp[m]==Max)		//取得最大拦截数量时 
		{
			b[n]=a[m];		//记录当前拦截高度 
			Max--;			 
			n+=1;			
		}
		m--;
	}

因题目要求数量过多,使用随机数代替输入
同时打印生成的a[N+1]便于查看
总的源代码如下:

#include<stdio.h> 
#include<stdlib.h>
#include<time.h>	
//#define N 100				//导弹的总个数 

int max(int a,int b)	//比较函数,返回大的值 
{
	if(a>=b)
		return a;
	else
		return b;
} 
 
int main()
{
	int N;
	printf("请输入来袭的导弹个数:"); 
	scanf("%d",&N);
	int i,j,m,n=1,Max=1;//m储存当取最大拦截数量时dp数组的系数 
	int a[N+1];		//储存每枚导弹的高度 
	int dp[N+1]	;			//dp[i]表示从1到第i枚最大拦截数量 
							//N+1表示数组的大小 从dp[0]~dp[N]共N+1个
	//printf("当前来袭导弹共有%d枚\n",N); 
	//printf("请依次输入导弹的高度:");
	printf("导弹的高度:\n");
	srand((unsigned)time(NULL));
	for(i=1;i<N+1;i++)		
	{
		a[i]=rand()%30000+1;
		//scanf("%d",&a[i]);	//依次输入每枚导弹的高度 
		printf("%8d",a[i]);
		if(i%8==0)
		printf("\n");
		dp[i]=1;			//拦截导弹数量的初值为1  即最少可以拦截本身
	}
	for(i=1;i<N+1;i++)
	{
		for(j=1;j<i;j++)	//遍历i前面的 
		{
			if(a[i]<a[j])		//后一枚高度低于前一枚   
			dp[i]=max(dp[i],dp[j]+1);	//当前拦截的最大数量与前面最大数量+1比较 取大的 
		}
	}
	for(i=1;i<N+1;i++)		//取最大拦截数量 
	{
		Max=max(Max,dp[i]);
		if(dp[i]==Max)
		m=i; 
	}
	printf("\n");
	printf("最大拦截数量Max=%d\n",Max);
	int b[Max+1];
	for(i=1;i<Max+1;i++)	//给数组b赋初值 
		{
			b[i]=0;		
		}
	while(m)		
	{
		if(dp[m]==Max)		//取得最大拦截数量时 
		{
			b[n]=a[m];		//记录当前拦截高度 
			Max--;			 
			n+=1;			
		}
		m--;
	}
	printf("\n拦截高度为:\n");
	j=1; 
	for(i=n-1;i>=1;i--)	//反向打印 
	{
		printf("%8d",b[i]);
		if(j%8==0)
		printf("\n");
		j++;
	} 
	 
}

例图
在这里插入图片描述

本文链接http://element-ui.cn/article/show-218956.aspx