算法学习之贪心算法（个人学习）

一、贪心算法的概念：

贪心算法总是做出当前看来是最好的选择。也就是说，贪心算法并不从整体最优上考虑，所作的选择只是在某种意义上的局部最优选择。

二、贪心算法的基本要素:

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

2、贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这个性质时贪心算法的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

三、例题之活动安排问题

活动安排问题是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动给。贪心提供了一个漂亮的方法，使得尽可能多的活动能兼容的使用公共资源

题目描述

“今年暑假不AC？”

“是的。”

“那你干什么呢？”

“看世界杯呀，笨蛋！”

“@#$%^&*%…”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。

作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

输入

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

输出

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

样例输入 Copy

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

样例输出 Copy

5

分析题目：为了满足看到尽量多的完整的节目，先看结束最早的，那开始肯定也是最早的，为了达到这个目的，我们先按照结束时间排序了。排完序后，比较一个结束时间和下一个开始时间，若结束时间小于开始时间，则这个下一个也要被看。依次比较下去，最后输出。

这里介绍一下选择结构体的作用：

• 可以将两个相关的整数（开始时间和结束时间）组合在一起，表示一个完整的节目。
• 通过结构体数组，可以一次性处理多个节目，而不是分别处理每个节目的开始和结束时间。
• 通过结构体内部的数据排序，可以方便地对节目按照结束时间进行排序，这是解决问题的一个重要步骤

#include
//结构体的定义
struct st{
    int start;
    int end;
};
int main()
{
    int n;
    
    struct st strr[101]={0};
    while(scanf("%d",&n)!=EOF)
    {
                
        int k=1;//记录能看的节目
        if(n==0)
        
            break;
        

    
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&strr[i].start,&strr[i].end);
    }
    //排序，从小到大，按照结束时间最早
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;jstrr[j].end)
            {
                //交换这两个的结束时间
                int t=0;
                t=strr[i].end;
                strr[i].end=strr[j].end;
                strr[j].end=t;
                //交换这两个的开始时间
                int m=0;
                m=strr[i].start;
                strr[i].start=strr[j].start;
                strr[j].start=m;
                
                
                
            }
        }
    }
    int fi=strr[0].end;//记录第一个结束时间
    //从第二个开始循环，这时k=1，因为第一个肯定要看的
    for(int i=1;i=fi){
            //可以看
            k++;
            //把这个可以看的结束时间给fi，下一次比较下一个的开始时间和这个的结束时间比
            fi=strr[i].end;
        }
    }
    printf("%d\n",k);
}
}

四、哈夫曼编码问题

哈夫曼编码时广泛用于数据文件压缩的十分有效的编码方法。其压缩率通常为20%~30%。哈夫曼编码算法用字符在文件中出现的频率表来建立了一个用0，1串表示各字符的最优表示方式。

它的编码思想是：根据各个字符使用的频率大小，以这些字符作为叶子结点构建一棵哈夫曼树，然后将树的所有左分支路径标记为0，右分支路径标记为1。这样从哈夫曼树的根结点到任何字符，所得到的0/1串都是唯一的，解码时不会出现二义性。

给出现频率高的字符较短的编码，出现频率较低的字符较长的编码，可以大大缩短总码长。

要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构性质

五、例题之一般背包问题（贪心算法与动态规划算法的差异）

0-1背包：给定n种物品，一个背包。物品i的重量是wi，价值是vi，背包容量是c，问，应如何选择装入背包的物品，使得转入背包中物品的总价值最大？

一般背包问题：与0-1类似，不同的是在选择物品i装入背包时，可以选择物品的一部分，而不是要全部装入背包。

虽然这两个问题很相似，但是一般背包问题可以用贪心算法求解，而0-1背包不能用。

用贪心算法求解一般背包问题的步骤：

1、计算每件物品单位重量的价值vi/wi（因为物品可分）

2、按照贪心的策略，选择单位重量价值最高的

3、若将这种物品全部转入背包后，物品的总价值未超过c，则选择次重的尽可能多地装入背包，依次策略，直至背包装满

下面给出一个例题：

题目描述

某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为W,的物品。岛上金属有s个种类, 每种金属重量不同，分别为n1,n2,n3 … ns，同时每个种类的金属总的价值也不同，分别为v1,v2, …vs。KID想一次带走价值尽可能多的金属，

问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。

输入

第1行是测试数据的组数k，后面跟着k组输入。 

每组测试数据占3行，第1行是一个正整数w(1<=w<=10000)，表示口袋承重上限。第2行是一个正整数s (1 <= s <=100)，表示金属种类。第3行有2s个正整数，分别为n1, v1, n2, v2, … , ns, vs分别为第一种，第二种，…，第s种金属的总重量和总价值(1<=ni<= 10000, 1<=vi<=10000)。 

输出

k行，每行输出对应一个输入。输出应精确到小数点后2位。

样例输入 Copy

2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43

样例输出 Copy

171.93
508.00

#include
int main()
{
    int n;
    scanf("%d",&n);
    while(n!=0)
    {
        int w;//背包上限
        int s;//物品种类
        int a[100001];//放重量
        float b[100001];//放每一种的价值
        double c[100001];//记录单位价值
        scanf("%d",&w);
        scanf("%d",&s);
        for(int i=0;i<s;i++)
        {
                scanf("%d",&a[i]);
            
                scanf("%f",&b[i]);
            
            
        }
      
        //记录单位价值
        for(int i=0;i<s;i++)
        {
            c[i]=b[i]/a[i];
        }
          
        //价值排序的同时，我们也需要对重量进行排序
        double r=0;
        int hei=0;
        for(int i=0;i<s;i++)
        {
            for(int j=i;j<s;j++)
            {
            if(c[i]<c[j])
            {
              
                r=c[i];
                c[i]=c[j];
                c[j]=r;
                
                hei=a[i];
                a[i]=a[j];
                a[j]=hei;
                
                
            }
            }
        }
        double record=0;//记录动态放取过程中背包总价值的变化
        for(int i=0;i<s;i++)
        {
            //重量小于背包容量，我们将全部放入
            if(a[i]<w)
            {
                record+=c[i]*a[i];
                //背包重量要减少
                w-=a[i];
            }
            //重量大于背包容量，只要取一部分
            else{
                record+=c[i]*w;
                break;
            }
        }
        printf("%.2f\n",record);
        n=n-1;
    }
    return 0;
}

易错点睛：

2s那个输入，只用写到s就行，在循环里写两个输入