贪心

一、基本概念

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

二、基本思路

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

三、适用问题

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

四、实现框架

从问题的某一初始解出发；

while （能朝给定总目标前进一步）

{

利用可行的决策，求出可行解的一个解元素；

}

由所有解元素组合成问题的一个可行解；

五、贪心策略的选择

因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。

哦，对了，导弹拦截了解一下

【题目】拦截导弹问题（NOIP1999）

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。

【输入格式】

n颗依次飞来的高度（1≤n≤1000）.

【输出格式】

要拦截所有导弹最小配备的系统数k。

【算法分析】

　　按照题意，被一套系统拦截的所有导弹中，最后一枚导弹的高度最低。设：

　　k为当前配备的系统数；

　　l[k]为被第k套系统拦截的最后一枚导弹的高度，简称系统k的最低高度（1≤k≤n）。

　　我们首先设导弹1被系统1所拦截（k←1,l[k]←导弹1的高度）。然后依次分析导弹2，…，导弹n的高度。

　　若导弹i的高度高于所有系统的最低高度，则断定导弹i不能被这些系统所拦截，应增设一套系统来拦截导弹I(k←k+1,l[k]←导弹i的高度)；若导弹i低于某些系统的最低高度，那么导弹i均可被这些系统所拦截。究竟选择哪个系统拦截可使得配备的系统数最少，我们不妨采用贪心策略，选择其中最低高度最小（即导弹i的高度与系统最低高度最接近）的一套系统p(l[p]=min{l[j]|l[j]>导弹i的高度}；l[p]←导弹i的高度)（1≤j≤k）。这样可使得一套系统拦截的导弹数尽可能增多。

　　依次类推，直至分析了n枚导弹的高度为止。此时得出的k便为应配备的最少系统数。

参考程序主要框架如下：

　k=1;l[k]=导弹1的高度;

for (i=2;i<=n;++i)

{ 　p=0;

　　　for (j=1;j<=k;++j)

if (l[j]>=导弹i的高度) { if (p==0) p=j;

　　　　　　　　　　　　　 else if (l[j]<l[p]) p=j;} //贪心

if (p==0) { ++k;l[k]=导弹i的高度; } //增加一套新系统

else l[p]=导弹i的高度; //贪心,更新第p套系统的最低高度

}

输出应配备的最少系统数K。

【总结】：

贪心的核心，想要解决这个问题，而这个问题又有许多局部问题，则求出局部最优解，从而推送到全局最优解
贪心一定要进行微微的证明

感谢各位与信奥一本通的鼎力相助！