一、基本概念：

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


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


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

二、贪心算法的基本思路：

    1.建立数学模型来描述问题。
    2.把求解的问题分成若干个子问题。
    3.对每一子问题求解，得到子问题的局部最优解。
    4.把子问题的解局部最优解合成原来解问题的一个解。

三、适用问题

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

四、实现框架 

    从问题的某一初始解出发；
    while （能朝给定总目标前进一步）
    { 
          利用可行的决策，求出可行解的一个解元素；
    }
    由所有解元素组合成问题的一个可行解；

五、贪心策略的选择

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

六、例题分析

 

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

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

【输入格式】
   n颗依次飞来的高度（1≤n≤1000）。
【输出格式】
   要拦截所有导弹最小配备的系统数k。
【输入样例】
   389 207 155 300 299 170 158 65
【输出样例】
   2

 【算法分析】

    按照题意，被一套系统拦截的所有导弹中，最后一枚导弹的高度最低。设：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的高度)（i≤j≤k）。这样可使得一套系统拦截的导弹数尽可能增多。
依次类推，直至分析了n枚导弹的高度为止。此时得出的k便为应配备的最少系统数。
本题算法适用贪心，参考程序如下：

 

k=1;[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的高度；	
}

 

 

输入应配备的最少系统数k