[动态规划]拦截导弹问题的一个疑问,没看懂解答

weichuang02

这个经典题目是:

【问题描述】
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然
它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到
敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算
(1)这套系统最多能拦截多少导弹
(2)如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

问题1就是求求最长非升子序列问题，标准的动态规划
问题2如何求解呢? 我看网上的答案都是这样说的:"其实认真分析一下题就回发现：每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装置无论如何也不能打那个导弹了，经过这么一分析，这个问题便抽象成在已知序列里找最长上升序列的问题。"

可是我实在是没有看明白，这个所谓的"这个问题便抽象成在已知序列里找最长上升序列的问题"是怎么分析出来的，大家能解释一下么?

hbmhalley

回复 3# weichuang02


    不是 .. 意思是你看到的那些话都只能说明答案不能少于是最长上升序列的长度，原因已经说了

    至于为什么答案恰好是这个长度，远不是这么一句就能说明的。证明在dilworth定理的证明中

    算了 .. 摘给你吧。这事其对偶定理的证明，也能说明问题：

    有一些导弹，不低于所有晚于它发射的导弹，称之为超级导弹
    注意，所有超级导弹是可以被一炮打光的

    把所有超级导弹拿走，放到第 1 个箱子里
    拿走后，现在又有了新的一批超级导弹，把它们放到第 2 个箱子里
    ...
    拿走最后一批超级导弹，放到第 p 个箱子里
    现在没导弹了，按照这个分法，p 炮可以打光所有导弹

    注意这个过程，为什么第 p 个箱子里的导弹不能放到第 p-1 个箱子里呢？ 因为在第 p-1 个箱子里存在一个晚于它但高于它的导弹。
    为什么 p-1 导弹不能放到 p-2 箱子里呢？同理。
    ...

    也就是说，任何 p 号箱子里的导弹 照这个方法数到 1 号箱子，都能数出一个时间递增且高度上升的序列。
    这个序列最长是多少？就是最长上升序列的长度。
    这个序列最短是多少？也是最长上升序列的长度。前面说过了。

hbmhalley

这只是个下限（必要性），因为 炮不能向上爬，所以最长上升序列里的两个导弹不可能被同一炮拦截，答案至少是其长度

至于其充分性，看 dilworth定理的证明吧

weichuang02

hbmhalley 发表于 2012-07-30 17:33
这只是个下限（必要性），因为 炮不能向上爬，所以最长上升序列里的两个导弹不可能被同一炮拦截，答案至少是 ...

谢谢。如果最大升序是6个元素，那么至少需要6套系统。

但问题是，数据当中可能远不止一个升序序列啊。问题(2)的算法应该如何设计和描述呢?

还望大虾继续指点!

starwing83

都说了是“最长”了，随意选取一个上升序列，可想而知每个炮弹都是要被打的，那么显然需要的最少设备套数是这个上升序列的元素个数，那么**最多**需要的设备套数显然就是当上升序列最长的时候的元素个数，这时需要的设备套数至少能将该上升序列的所有炮弹打下来。

但是这没有证明充分性（即有可能需要更多的设备>最长上升序列元素个数才能**全部**击落），证明思路见楼上。

weichuang02

hbmhalley 发表于 2012-07-30 19:31
回复 3# weichuang02

总结一下你说的:
(1)必要性: n>=k
(2)充分性: n<=k
所以n=k

多谢！