贪心算法 | 北温带的猫

五大常用算法——贪心算法详解以及经典例子

思维导图

概念

贪心算法（Greedy Alogorithm）又叫登山算法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但是适用范围有限的策略。贪心算法没有固定的框架，算法设计的关键是贪婪策略的选择。贪心策略要无后向性，也就是说某状态以后的过程不会影响以前的状态，至于当前状态有关。
贪心算法是对某些求解最优解问题的最简单、最迅速的技术。某些问题的最优解可以通过一系列的最优的选择即贪心选择来达到。但局部最优并不总能获得整体最优解，但通常能获得近似最优解。
在每一部贪心选择中，只考虑当前对自己最有利的选择，而不去考虑在后面看来这种选择是否合理。

解题步骤

从问题的某个初始解出发
采用循环语句，党可以向求解目标前进一步时，就根据局部最优策略，得到一个不分解，缩小问题的范围或规模。
将所有的部分解综合起来，得到问题的最终解。

贪心策略的选择

贪心算法的原理是通过局部最优来达到全局最优，采用的是逐步构造最优解的方法。在每个阶段，都做出一个看上去最优的，决策一旦做出，就不再更改。
要选出最优解可不是一件容易的事，要证明局部最优为全局最优，要进行数学证明，否则就不能说明为全局最优。
很多问题表面上看来用贪心算法可以找到最优解，实际上却把最优解给漏掉了。这就像现实生活中的“贪小便宜吃大亏”。所以我们在解决问题的时候，一定要谨慎使用贪心算法，一定要注意这个问题适不适合采用贪心算法。

贪心策略应考虑的问题

候选集合S
为了构造问题的解决方案，有一个候选集合C作为问题的可能解，问题的最终解均取自于候选集合C。
解集合S
随着贪心选择的进行，解集合不断扩展，直到构成一个满足问题的完整解。
解决函数solution
检查解集合是否构成问题的完整解。
选择函数select
即贪心策略，这是贪心算法的关键，它指出哪个候选对象有希望构成成问题的解。
可行函数feasible
检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。

例题会场安排

问题描述

假设有一个会场，现要求此会场中安排尽可能多的活动，求会场中所能安排的活动的最多数，并给出安排方案。

输入要求

第一行n为所有活动数，随后n行，每行两个数，分别为活动的开始和结束时间。

测试用例

算法思想

将活动的结束时间从小到大进行排序，先选择结束时间最早的活动，然后看下一个活动的开始时间是否晚于上一个被选中活动的结束时间，若是，则选中该活动；否则不选中。直到所有的活动都遍历了一遍。

贪心选择性的证明

代码

#include<stdlib.h>
void finshpx(int n,int *begin,int *finsh);
void greedy(int n,int *begin,int *finsh,int *a);
int main()
{
    int n, *begin, *finsh;			//分别记录开始时间 结束时间
    int *a;			//记录是否被选中
    	scanf("%d", &n);
    begin = (int *) malloc(sizeof(int ) *n);
    finsh = (int *) malloc(sizeof(int ) *n);
    a = (int*) malloc(sizeof(int) *n);
    	for(int i = 0; i < n; i++) 
    scanf("%d%d", &begin[i], &finsh[i]);
    	for(int i = 0; i < n; i++) 
    greedy(n, begin, finsh, a);
    return 0;
}
void greedy(int n,int *begin,int *finsh,int *a)
{
    finshpx(n, begin, finsh);			//按结束时间进行排序
    a[0] = 1;
    int count = 1;
    int endtime = finsh[0];
    for(int i = 1; i < n; i++) 
    {
        if(begin[i] >= endtime) 
        {
            endtime = finsh[i];
            count++;
            a[i] = 1;
        }
        else 
        a[i] = 0;
    } 
    printf("最多容纳个%d活动\n", count);
    printf("分别为：");
    for(int i = 0; i < n; i++) 
    	if(a[i] == 1) 
    		printf("%d ", i + 1); 
}
void finshpx(int n,int *begin,int *finsh)			//冒泡排序
{
    for(int i = 1; i < n; i++) 
    for(int j = 0; j < n - i; j++) 
    {
        if(finsh[j] > finsh[j + 1]) 
        {
            int t = finsh[j];
            finsh[j] = finsh[j + 1];
            finsh[j + 1] = t;
            t = begin[j];
            begin[j] = begin[j + 1];
            begin[j + 1] = t;
        }
    } 
}