什么是贪心算法

关于贪心算法，我听说过好几次了，但是不知道为什么总是想到贪吃蛇，今天我才知道算法讲的什么意思，根据我们老师的ppt讲义，原理很简单，大部分都是例子，但是我感觉掌握还是要下功夫的，重点在于如何针对特定的问题进行贪心，某类问题是否适合用贪心算法计算，这两点感觉是难点。

算法思想

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

话虽这样说，但是我感觉还是存在很多疑惑，因为都是对特定的问题求解，我自然联想到了前面学习的枚举类型的使用，看了几个ppt的例子，无意间想到了前面枚举应用的时候那

个“01背包问题”，是否可以用贪心算法来解决？我的思考是不行，因为我自己能够找到如果利用贪心算出错误结果的情况，而且是很好列举的。贪心算法解决的问题是否可以用枚

举的方式来解决，枚举算法解决的问题是否又可以用贪心算法来解决，如果两者都可以的话，那个效率会更高？如果对于一类问题只能用这两种办法其中的一个进行处理，原因是

什么？这些都是我不知的，也是要学习的。

下面是里面的一些案例

1.最优装载问题

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

思路：根据贪心算法的思想，这里应该是每次先选择小的先装上，一直到超过限制就停止，最后输出编号就行了。代码不难，如下：

#include#includetypedef struct//定义集装箱结构体
{
    int weight;
    int num;
}W;
int comp(const void*a,const void *b)
{
    return ((W*)a)->weight-((W*)b)->weight;
}
int main()
{
    W a[10];
    int i,j=0;
    int n=0;
    int m;
    int sum=0;
    printf("请输入集装箱的个数:n");//方便测试不超过10
    scanf("%d",&m);
    printf("输入重量的最大限制:n");
    scanf("%d",&n);
    printf("请输入每个集装箱的重量");
    for(i=0;i<m;i++)
    {
        scanf("%d",&a[i].weight);
        a[i].num=i+1;
    }
    qsort(a,m,sizeof(W),comp);//先排序
    for(i=0;i<m;i++)//然后从小到大加起来
    {
        if(sum<=n)
        sum+=a[i].weight;
        else
        {
            j=i;
            break;//记录最后的值
        }
    }
    for(i=0;i<j;i++)
    {
        printf("第%d号: %dn",a[i].num,a[i].weight);
    }
    return 0;
}

2背包问题

这个问题和前面枚举里面提到的背包问题很类似，但是不是一个问题。

现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

最大的区别就是背包问题里面提到的物品是可以分割的，物品的价值是单位重量的价值，枚举类型的01背包问题，01背包问题的价值是物品的价值，物品是不可以分割的。

因为不可分割，所以所以产生的解应该是分立的，不是连续的，有穷个，但是如果是可以分割，可能情况为无穷多种，所以这里不适合枚举。这样情况下用贪心算法好。在既可

以用枚举的情况下，用可以用贪心的情况下，枚举无疑是最精确的，贪心算法只能求最优解的近似解，自己目前还不能针对具体情况分的非常清楚，只能根据ppt里提到的及几

种贪心算法的几个实例。以后继续学习。

#include#includetypedef struct
{
    int val;//单位价值
    int weight;
}PRO;
int comp(const void *a,const void *b)
{
    return ((PRO*)b)->val-((PRO*)a)->val;
}
int main()
{
    PRO a[10];
    int i=0;
    int m,n;
    int val_sum=0;
    int weight_sum=0;
    printf("输入物品种类数目:n");
    scanf("%d",&n);
    printf("依次输入重量和价值:n");
    for(i=0;i<n;i++)
    {
        scanf("%d %d",&a[i].weight,&a[i].val);
    }
    printf("输入重量的限制:n");
    scanf("%d",&m);
    qsort(a,n,sizeof(PRO),comp);
    for(i=0;i<n&&(weight_summ)
    {
        val_sum-=(weight_sum-m)*a[i-1].val;
    }
    printf("%d",val_sum);
}

亏损问题 题目的意思就是如果公司盈利，那么就盈利s，如果亏损，那么就亏损d。但是公司只是5个月结算一次，也就是说是1——5月，2——6 月……，只结算这8次。但是公司的这一年的8次结算下来，公司都是亏损了，问，公司这一年是否能够盈利，如果能，求出最大的盈利利润，如果不能，则输出Deficit。

第一眼一看，实在是看不出和前面的贪心算法有什么联系，而且感觉肯定是赔定了。但是不是。

分析思路

取每次总结的5个月份，进行排列组合应该没有先后顺序，因为就是进行加法计算，减法计算，赚和赔的顺序无关紧要（对于一次调查来说）

只可能是下列结果,没有其他的了

s s s s d    4*s-d<0

s s s d d     3*s-2*d<0

s s d d d     2*s-3*d<0

s d d d d    s-4*d<0

如果这些里面没有赚钱的，这个公司不可能赚钱了

如果赚钱的或者最赚钱的存在肯定是上面情况的一种，一年内赚钱最多的是上面某一种，那么按照保证每次调查都是上面的形式就可以保证赚钱最大了。

s s s s d s s s s d s s

s s s d d  s s s d d s s

s s d d d s s d d d s s

s d d d d s d d d d  s d 

可见只要计算根据上面情况下s和d是不是也满足相应的条件就行，如果满足就把12个月的加起来，看看是不是赚，然后找出赚的最大值就行了。

#include#includeint main()
{
   int s,d,i,j,tem=0;
   int max_val=0;
   printf("输入赚钱和赔钱的数目n");
   scanf("%d %d",&s,&d);
   for(i=1;i<5;i++)
   {
       tem=(5-i)*s-i*d;
       if(tem=2)
           {
               tem=tem*2+2*s;
           }
           else
           {
               tem=tem*2+s-d;
           }
           if(max_val0)
   {
       printf("赚钱n");
       printf("%d*s-%d*dn",j,5-j);
       printf("%d",max_val);
   }
   else
   {
       printf("赔钱n");
   }
}