导弹拦截系统-动态规划C语言实现

目录

导弹拦截问题背景

1.问题描述

2.动态规划思路

3.用最少数量的系统拦截所有导弹

 4.代码实现

 5.运行结果

导弹拦截问题背景

假设有一个国家部署了一系列导弹防御系统，每个系统有其特定的拦截高度范围。同时，敌人发射了一系列导弹，每个导弹也有其特定的飞行高度。为了成功拦截所有导弹，必须为每个导弹找到一个能够覆盖其飞行高度的防御系统。然而，为了高效利用资源，希望用最少数量的防御系统来拦截所有导弹。        

在导弹拦截系统中，动态规划可以用于解决如何有效地拦截来袭导弹的问题。具体来说（敲黑板画重点），这个问题可以转化为寻找一个最长递减子序列（Longest Non-Increasing Subsequence，LNIS）和最长递增子序列（Longest Increasing Subsequence，简称LIS）的问题。

最长递增子序列转博客：最长递增子序列问题（动态规划）c语言实现_给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。-CSDN博客

1.问题描述

        给定一个导弹的高度序列，要求找出一个最长的子序列，使得该子序列中的导弹高度按照时间顺序（即来袭顺序）递减或保持不变，最少需要都是套系统才能拦截所有的导弹，也就是最长递增子序列长度。

2.动态规划思路

        定义一个数组dp，其中dp[i]表示以第i个导弹结尾的最长不增子序列的长度。
初始化dp数组，将每个dp[i]都设为1，因为每个导弹本身都可以看作是一个长度为1的不增子序列。
遍历导弹高度序列，对于每个导弹i，再遍历它之前的所有导弹j（j<i），如果导弹j的高度大于等于导弹i的高度（a[j]>=a[i]），则更新dp[i]为dp[j]+1（如果dp[j]+1大于dp[i]的话）。
在遍历过程中，记录dp数组中的最大值，这个最大值就是以任意导弹结尾的最长不增子序列的长度，也就是系统最多能拦截的导弹数量。

3.用最少数量的系统拦截所有导弹

        意味着找到一个最小的集合（即“子序列”），使得集合中的每个元素（防御系统）都能“覆盖”（即拦截）至少一个导弹，且这些导弹的飞行高度构成一个递增序列（因为每个防御系统通常只能覆盖一个高度区间，为了拦截更多导弹，系统覆盖的高度区间需要逐步上升）。

 4.代码实现

#define MAXNUM 30
#define MAX(a, b) ((a) > (b) ? (a) : (b))  

int main() {
	int missile[MAXNUM] = { 999,888,899,777,666,632,555,590 };
	int dpRise[MAXNUM] = { 0 };
	int dpFall[MAXNUM] = { 0 };
	int height = 0;
	int ans = 0; // 记录最多能拦截多少导弹
	int ans2 = 0; // 记录拦截所有导弹最少要配备多少系统 
	int number = 8;
	for (int i = 0; i < number; i++) {
		dpRise[i] = 1;
		dpFall[i] = 1;
		for (int j = 0; j < i; j++) {
			if (missile[j] >= missile[i]) {
				dpRise[i] = MAX(dpRise[j] + 1, dpRise[i]);//最长递减子序列
			}
			else {
				dpFall[i] = MAX(dpFall[j] + 1, dpFall[i]);//最长递增子序列
			}
		}
		if (ans <= dpRise[i])
		{
			ans = dpRise[i];
			height = i;//记录最后一个拦截的高度
		}
		ans2 = MAX(ans2, dpFall[i]);
	}
	int tmp = 0;
	printf("拦截的各导弹高度是多少:");
	for (int i = height; i >= 0; i--)
	{
		if (dpRise[i] != tmp)
			printf("%d ", missile[i]);
		tmp = dpRise[i];
	} 
	printf("\n最长拦截的长度为：%d\n", ans);
	printf("最少要配备的系统数为：%d\n", ans2);
	return 0;
}

 5.运行结果