01基本概念

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

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

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

02贪心算法的基本思路

解题的一般步骤是：

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

03该算法存在的问题

• 不能保证求得的最后解是最佳的

• 不能用来求最大值或最小值的问题

• 只能求满足某些约束条件的可行解的范围

04贪心算法适用的问题

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

实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。

05贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

06贪心算法的实现框架

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

while (朝给定总目标前进一步){   利用可行的决策，求出可行解的一个解元素。}

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

07例题分析

这是《算法导论》上的例子，也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。



考虑使用贪心算法的解法。为了方便，我们用不同颜色的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝色的线条表示我们已经选择的活动；红色的线条表示我们没有选择的活动。

如果我们每次都选择开始时间最早的活动，不能得到最优解：



如果我们每次都选择持续时间最短的活动，不能得到最优解：



可以用数学归纳法证明，我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。

#include#include#includeusing namespace std;    int N;struct Act{  int start;  int end;}act[100010];
bool cmp(Act a,Act b)  {    return a.end}
int greedy_activity_selector()  {    int num=1,i=1;     for(int j=2;j<=N;j++)    {      if(act[j].start>=act[i].end)      {        i=j;        num++;      }    }    return num;}
int main()  {    int t;  scanf("%d",&t);  while(t--)  {    scanf("%d",&N);    for(int i=1;i<=N;i++)    {      scanf("%lld %lld",&act[i].start,&act[i].end);    }    act[0].start=-1;    act[0].end=-1;    sort(act+1,act+N+1,cmp);    int res=greedy_activity_selector();    cout<endl;    }}  

#include#includeusing namespace std;const int N=7;int Count[N]={3,0,2,1,0,3,5};int Value[N]={1,2,5,10,20,50,100};
int solve(int money){  int num=0;  for(int i=N-1;i>=0;i--)  {    int c=min(money/Value[i],Count[i]);    money=money-c*Value[i];    num+=c;  }  if(money>0) num=-1;  return num;}
int main(){  int money;  cin>>money;  int res=solve(money);  if(res!=-1) cout<endl;  else cout<<"NO"<<endl;}

#include   using namespace std;   const int N=4;  void knapsack(float M,float v[],float w[],float x[]);  
int main()  {    float M=50;  //背包所能容纳的重量     float w[]={0,10,30,20,5};  //每种物品的重量    float v[]={0,200,400,100,10};    //每种物品的价值  float x[N+1]={0};    //记录结果的数组  knapsack(M,v,w,x);    cout<<"选择装下的物品比例："<<endl;    for(int i=1;i<=N;i++) cout<<"["<"]:"<endl;  }  
void knapsack(float M,float v[],float w[],float x[])  {    int i;    //物品整件被装下    for(i=1;i<=N;i++)  {      if(w[i]>M) break;       x[i]=1;      M-=w[i];    }     //物品部分被装下    if(i<=N) x[i]=M/w[i];   }

#include  #include    using namespace std;  int speed[10010];  int mintime[110];  
bool cmp( const int &x,const int &y)  {    return x>y;  }  
int main()  {    int n,m;           memset(speed,0,sizeof(speed));    memset(mintime,0,sizeof(mintime));    cin>>n>>m;    for(int i=0;icin>>speed[i];    sort(speed,speed+n,cmp);    for(int i=0;i  {    *min_element(mintime,mintime+m)+=speed[i];     }     cout<<*max_element(mintime,mintime+m)<<endl;}

#include#includeusing namespace std;
int main(){  int a[1000],t,n,sum;  scanf("%d",&t);  while(t--)  {    scanf("%d",&n);    sum=0;    for(int i=0;iscanf("%d",&a[i]);    while(n>3)    {      sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);      n-=2;    }    if(n==3) sum+=a[0]+a[1]+a[2];    else if(n==2) sum+=a[1];    else sum+=a[0];    printf("%d
",sum);  }}

POJ1328是一道经典的贪心算法例题。题目大意是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。对于每个小岛，我们可以计算出一个雷达所在位置的区间。



问题转化为如何用尽可能少的点覆盖这些区间。先将所有区间按照左端点大小排序，初始时需要一个点。如果两个区间相交而不重合，我们什么都不需要做；如果一个区间完全包含于另外一个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。

AC代码：

#include#include#includeusing namespace std;struct Point{  double x;  double y;}point[1000];
int cmp(const void *a, const void *b){  return (*(Point *)a).x>(*(Point *)b).x?1:-1;}
int main(){  int n,d;  int num=1;  while(cin>>n>>d)  {    int counting=1;    if(n==0&&d==0) break;    for(int i=0;i    {      int x,y;      cin>>x>>y;      if(y>d)      {        counting=-1;      }      double t=sqrt(d*d-y*y);      //转化为最少区间的问题      point[i].x=x-t;      //区间左端点      point[i].y=x+t;      //区间右端点    }    if(counting!=-1)    {      qsort(point,n,sizeof(point[0]),cmp);      //按区间左端点排序      double s=point[0].y;      //区间右端点      for(int i=1;i      {        if(point[i].x>s)          //如果两个区间没有重合,增加雷达数目并更新右端点        {          counting++;          s=point[i].y;        }        else if(point[i].y          //如果第二个区间被完全包含于第一个区间,更新右端点        {          s=point[i].y;        }      }    }    cout<<"Case "<':'<<' '<endl;    num++;  }}

#include#include#include#include#include#include#includeusing namespace std;long long int price[100010],t,n,res;
int main(){  ios::sync_with_stdio(false);  cin>>t;  while(t--)  {    cin>>n;    priority_queue<long long int, vector<long long int>, greater<long long int> > q;    res=0;    for(int i=1;i<=n;i++)    {      cin>>price[i];    }    res-=price[1];    res+=price[n];    for(int i=2;i<=n-1;i=i+2)    {      long long int buy=min(price[i],price[i+1]);      long long int sell=max(price[i],price[i+1]);      if(!q.empty())      {        if(buy>q.top())        {          res=res-2*q.top()+buy+sell;          q.pop();          q.push(buy);          q.push(sell);        }        else        {          res=res-buy+sell;          q.push(sell);        }      }      else      {        res=res-buy+sell;        q.push(sell);      }    }         cout<endl;  }}

#include#include#includeusing namespace std;
int main(){  long long int sum;  int i,n,t,a,b;  while(~scanf("%d",&n))  {    priority_queue<int,vector<int>,greater<int> >q;    for(i=0;i    {      scanf("%d",&t);      q.push(t);    }    sum=0;    if(q.size()==1)    {      a=q.top();      sum+=a;      q.pop();    }    while(q.size()>1)    {      a=q.top();      q.pop();      b=q.top();      q.pop();      t=a+b;      sum+=t;      q.push(t);    }    printf("%lld
",sum);  }}

#include#include#define INF 1000#define MAX_V 100using namespace std;  
int main(){  int V,E;  int i,j,m,n;  int cost[MAX_V][MAX_V];  int d[MAX_V];  bool used[MAX_V];  cin>>V>>E;  fill(d,d+V+1,INF);  fill(used,used+V,false);  for(i=0;i  {    for(j=0;j    {      if(i==j) cost[i][j]=0;      else cost[i][j]=INF;    }  }  for(m=0;m  {    cin>>i>>j>>cost[i][j];    cost[j][i]=cost[i][j];  }  cin>>n;  d[n]=0;  //源点  while(true)  {    int v=V;    for(m=0;m    {          if((!used[m])&&(d[m]    }        if(v==V) break;    used[v]=true;    for(m=0;m    {      d[m]=min(d[m],d[v]+cost[v][m]);    }  }  for(i=0;i  {    cout<<"the shortest distance between "<" and "<" is "<endl;  }}

构造最小生成树的Kruskal算法和Prim算法都利用了MST(最小生成树)性质：设顶点集U是V的真子集(可以任意选取)，如果(u,v)∈E为横跨点集U和V—U的边，即u∈U，v∈V- U，并且在所有这样的边中，(u,v)的权c[u][v]最小，则一定存在G的一棵最小生成树，它以(u,v)为其中一条边。




使用反证法可以很简单的证明此性质。假设对G的任意一个最小生成树T，针对点集U和V—U，(u,v)∈E为横跨这2个点集的最小权边，T不包含该最小权边，但T包括节点u和v。将添加到树T中，树T将变为含回路的子图，并且该回路上有一条不同于的边,u’∈U,v’∈V-U。将删去，得到另一个树T’，即树T’是通过将T中的边替换为得到的。由于这2条边的耗费满足c[u][v]≤c[u’][v’]，故即T’耗费≤T的耗费，这与T是任意最小生成树的假设相矛盾，从而得证。



Prim算法每一步都选择连接U和V-U的权值最小的边加入生成树。

#include#include#define MAX_V 100#define INF 1000using namespace std;  
int main(){  int V,E;  int i,j,m,n;  int cost[MAX_V][MAX_V];  int mincost[MAX_V];  bool used[MAX_V];  cin>>V>>E;  fill(mincost,mincost+V+1,INF);  fill(used,used+V,false);  for(i=0;i  {    for(j=0;j    {      if(i==j) cost[i][j]=0;      else cost[i][j]=INF;    }  }  for(m=0;m  {    cin>>i>>j>>cost[i][j];    cost[j][i]=cost[i][j];  }  mincost[0]=0;  int res=0;  while(true)  {    int v=V;    for(m=0;m    {          if((!used[m])&&(mincost[m]        v=m;    }        if(v==V) break;    used[v]=true;    res+=mincost[v];    for(m=0;m    {      mincost[m]=min(mincost[m],cost[v][m]);    }  }  cout<endl;}

Kruskal算法每一步直接将权值最小的不成环的边加入生成树，我们借助并查集这一数据结构可以完美实现它。

#include#include#define MAX_E 100using namespace std;  struct edge{  int u,v,cost;    };int pre[MAX_E];edge es[MAX_E];int find(int x);void initvalue(int x);bool same(int x,int y);void unite(int x,int y);bool comp(const edge& e1,const edge& e2);
int main(){  int V,E;  int i,j,m,n;  cin>>V>>E;  initvalue(V);  for(i=0;icin>>es[i].u>>es[i].v>>es[i].cost;          sort(es,es+E,comp);  int res=0;  for(i=0;i  {    edge e=es[i];    if(!same(e.u,e.v))    {      unite(e.u,e.v);      res+=e.cost;    }  }  cout<endl;    }
bool comp(const edge& e1,const edge& e2){  return e1.cost}
void initvalue(int x){  for(int i=0;i}
int find(int x){  int r=x;  while(pre[r]!=r) r=pre[r];  int i=x,j;  while(pre[i]!=r)  {    j=pre[i];    pre[i]=r;    i=j;  }  return r;}
bool same(int x,int y){  if(find(x)==find(y)) return true;  else return false;    }
void unite(int x,int y){  int fx=find(x);  int fy=find(y);  if(fx!=fy) pre[fx]=fy;    }

审核编辑：汤梓红