贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

例题1：

拿到题目，看到了几个关键信息：
1:某一行可能有多个脚注；

2:正文（行）必须和其拥有的脚注在同一页；

所以，我们可以这样分析，问题只可能有两种情况：
1：当前页可以容纳当前行与其脚注；
2：当前页不可以容纳当前行与其脚注；

碰到情况1时就没什么好说的了，而碰到情况2时，我们就将页数+1，并容纳这一行；

#include<stdio.h>
int f[1001];
int x,y;
int p=0;
int tmp=1;
int main()
{
    int m,n,a;
    scanf("%d%d%d",&m,&n,&a);
    for(int i=1;i<=a;i++)
    {
        scanf("%d%d",&x,&y);
        f[x]=y+f[x];             
    }
    for(int i=1;i<=m;i++)
    {
        if(p+f[i]+1<n)
        {
            p=p+f[i]+1;
  
        }
        else
        if(p+f[i]+1==n&&i<m)
        {
            p=0;
            tmp++;
  
        }
        else
        if(p+f[i]+1>n)
        {
            p=f[i]+1;
            tmp++;
  
        }       
    } 
    printf("%d",tmp);   
}

例题2：

这道题的分析如下：
1:先按照拥有的花生个数，将植株由大到小排序；
2:判断是否能采集到最大的植株：
时间需要大于 一个来回+1(采摘时间)
因为可以从任意列出发，所以就从拥有最多花生的植株那列出发；
如果不能，输出0；
3:判断是否能够采摘更多的花生：
时间需要大于 到达次大的花生植株+从次大的植株返回路边+1（采摘时间）;
如果不能，当前采摘到的花生即为答案；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct your
{
    int c,x,y;  
}a[40010];
bool cmp(your j,your k)
{
    return j.c>k.c;
}
int m,n,k,t;
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int tmp;
            scanf("%d",&tmp);
            if(tmp>0)
            {
                k++;
                a[k].c=tmp;
                a[k].x=i;
                a[k].y=j;
            }
        }
    }
    sort(a+1,a+k+1,cmp);
    int ans=0;
    int l=2;
    if(t>=a[1].x*2+1)
    {
        t=t-a[1].x-1;
        ans=a[1].c+ans;
        while(l<=k)
        {
            if(t>=abs(a[l-1].x-a[l].x)+abs(a[l-1].y-a[l].y)+a[l].x+1)
            {
                t=t-abs(a[l-1].x-a[l].x)-abs(a[l-1].y-a[l].y)-1;
                ans=ans+a[l].c;
            }
            else
            {
                break;
            }
            l++;
        }
    }
    printf("%d",ans);
}

例题3：

POJ3045 Cow Acrobats(贪心)

u证明:

设Di表示第i头奶牛的难受值，Wi表示第i头奶牛的体重，Si表示第i头奶牛的力量，令i,j相邻，且Wi+Si>Wj+Sj，设∑表示i和j上面的奶牛的重量之和

当i在j的上方时有，Di=∑−Si ①，Dj=∑+Wi−Sj ②，当j在i的上方时有，Di=∑+Wj−Si ③，Dj=∑−Sj ④，显然我们可以得到，③>①,②>④,②>③，这里面②最大，所以如果我们让i在j的上方最终答案一定不会更优，即证得此贪心策略的正确性。

注意有可能为负数！！！

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
long long sum;
long long ans=-0x7f7f7f7f;
struct your
{
    int w,s;
}a[50005];
bool cmp(your j,your k)
{
    return j.w+j.s<k.w+k.s; 
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].w,&a[i].s);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(ans<=sum-a[i].s) ans=sum-a[i].s;
        sum+=a[i].w;
    }
    printf("%lld",ans);
    return 0;
}

 

 

未完待续......（刷水题去也！