简单贪心

贫心法是求解一类最优化问题的方法， 它总是考虑在当前状态下局部最优(或较优)的策略，来使全局的结果达到最优(或较优)。显然，如果采取较优而非最优的策略(最优策略可能不存在或是不易想到)，得到的全局结果也无法是最优的。而要获得最优结果，则要求中间的每步策略都是最优的，因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法，即假设策略不能导致最优解，然后通过一系列推导来得到矛盾，以此证明策略是最优的，最后用数学归纳法保证全局最优。不过对平常使用来说，也许没有时间或不太容易对想到的策略进行严谨的证明( 贪心的证明往往比贪心本身更难)，因此一般来说，如果在想到某个似乎可行的策略，并且自己无法举出反例，那么就勇敢地实现它。

下面来看两个简单的例子。

思路:
按照价格的高低排序
然后依次拿当前最高的。直到满足需要的。

#include<cstdio>
#include<algorithm>
using namespace std;
struct moon
{
    double weight;
    double money;
    double a;
}m[1035];
bool cmp(moon a,moon b)
{
	return a.a<b.a;
}
int main(void)
{
    int N;
    double D;
    double sum=0;
    scanf("%d %lf",&N,&D);
    int i,j;
    for(i=0;i<N;i++)
    {
        scanf("%lf",&m[i].weight);
    }
    for(i=0;i<N;i++)
    {
        scanf("%lf",&m[i].money);
        m[i].a=m[i].money/m[i].weight;
    }
    sort(m,m+N,cmp);
    for(i=N-1;i>=0;i--)
    {
        if(m[i].weight>D)
        {
            printf("%.2f\n",m[i].a*D+sum);
			return 0;
        }
        else
        {
            D=D-m[i].weight;
            sum=sum+m[i].money;
        }
    }
    if(D!=0)//说明库存不足
    {
           printf("%.2lf",sum);
    }
    return 0;
}

思路:
找到1~9中最小的数输出。且此数的次数减1
然后从0~9依次输出数字

#include<cstdio>
int a[15];
int main(void)
{
    int i;
    int min=0;
    for(i=0;i<10;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<10;i++)
    {
        if(a[i]!=0)
        {
            min=i;//找到了1~9中最小的数
            break;
        }
    }
    printf("%d",min);
    a[min]--;
    for(i=0;i<10;i++)//按照顺序此次输出
    {
    	while(a[i]!=0)
        {
        	printf("%d",i);
        	a[i]--; 
        }
    }
    return 0;
}

区间贪心

通过上面的例子，读者可以对贪心有个大致的了解。
下面来看一个稍微复杂点的向题.即区间不相交问题:给出N个开区同(x,y)从中选择尽可能多的开区间，使得这些开区间两两没有交集。
例如对开区间(1, 3)、(2,4). (3,5). (6, 7)来说，可以选出最多三个区间(1,3).(3,5)、 (6,7), 它们互相没有交集。
首先考虑最简单的情况，如果开区间a1被开区间a2包含，如图1所示，那么显然选择a1是最好的选择，因为如果选择a1,那么就有更大的空间去容纳其他开区间。
接下来把所有开区间按左端点x从大到小排序，如果去除掉区间包含的情况，那么一定有y1>y2> … yn成立，如图2所示。现在考虑应当如何选取区间。通过观察会发现，i1的右边有一段是一定不会和其他区间重叠的， 如果把它去掉，那么i1的左边剩余部分就会被i2包含，由图2的情况可知，应当选择i1因此对这种情况，总是先选择左端点最大的区间。

大致思路:
就是按左端点由大到小排，左端点相等。按右端点从小到大排 。
然后选择和判断下一个区间的右端点会不会和上一个区间的左端点大。
大的话不选，小的话选。标记这个选的区间的左端点，接着依次类推。

#include<cstdio>
#include<algorithm>
using namespace std;
int number=1;//统计个数 
struct student
{
	int left;//左 
	int right;//右 
}stu[100];
bool cmp(student a,student b)
{
	if(a.left==b.left)//左端点相等。按右端点从小到大排 
		return a.right<b.right;
	return a.left>b.left;//左端点从大到小排 
}
int main(void)
{
    int n;
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    	scanf("%d %d",&stu[i].left,&stu[i].right);
    }
    sort(stu,stu+n,cmp);
    int leftx=stu[0].left;//记录上一个被选中的左端点 
    printf("(%d,%d)\n",stu[0].left,stu[0].right);
    for(i=1;i<n;i++)
    {
    	if(leftx>=stu[i].right)//可以选 
    	{
    		number++;
    		leftx=stu[i].left;
    		printf("(%d,%d)\n",stu[i].left,stu[i].right);
    	}		
    }
    printf("%d\n",number);
    return 0;
}

值得注意的是，总是先选择右端点最小的区间的策略也是可行的，
读者可以模仿上面的思路推导一下过程， 并写出相应的代码。

#include<cstdio>
#include<algorithm>
using namespace std;
int number=1;//统计个数 
struct student
{
	int left;//左 
	int right;//右 
}stu[100];
bool cmp(student a,student b)
{
	if(a.right==b.right)//右端点相等。按左端点从大到小排 
		return a.left<b.left;
	return a.right<b.right;//右端点从小到大排 
}
int main(void)
{
    int n;
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    	scanf("%d %d",&stu[i].left,&stu[i].right);
    }
    sort(stu,stu+n,cmp);
    int rightx=stu[0].right;//记录上一个被选中的右端点 
    printf("(%d,%d)\n",stu[0].left,stu[0].right);
    for(i=1;i<n;i++)
    {
    	if(rightx<=stu[i].left)//可以选 
    	{
    		number++;
    		rightx=stu[i].right;
    		printf("(%d,%d)\n",stu[i].left,stu[i].right);
    	}		
    }
    printf("%d\n",number);
    return 0;
}

与这个问题类似的是区间选点问题:
给出N个闭区间[x,y)求最少需要确定多少个点，才能使每个闭区间中都至少存在一个点。
例如对闭区间[1,4]、[2,6]. [5, 7]来说，需要两个点(例如3、5)才能保证每个闭区间内都有至少有一个点。
这个问题说白了也就是看有几个不相交的区间问题。
事实上，这个问题和区间不相交问题的策略是一致的。 首先，回到图1,如果闭区间a1被闭区间a2包含，那么在a1中取点可以保证这个点一定在a2内。接着把所有区间按左端点从大到小排序，去除掉区间包含的情况，就可以得到图2。显然，由于每个闭区间中都需要存在一个点，因此对左端点最大的区间 i1 来说，取哪个点可以让它尽可能多地覆盖其他区间?很显然，只要取左端点即可，这样这个点就能覆盖到尽可能多的区间。区间选点问题的代码只需要把区间不相交问题代码中的“stu[i].right<= leftx"改为“stu[i].right < leftX"即可，读者可以思考一下为什么。

总的来说，贪心是用来解决一类最优化问题， 并希望由局部最优策略来推得全局最优结果的算法思想。贪心算法适用的问题一定满足最优子结构性质， 即个问题的最优解可以由它的子问题的最优解有效地构造出来。
显然， 不是所有问题都适合使用贫心法，但是这并不妨碍贪心算法成为一个简洁、 实用、高效的算法。