贪心算法

思维导图

概念

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

解题步骤

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

贪心策略的选择

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

贪心算法很多时候并不能达到全局最优，为什么我们还要使用它呢？

因为在很多大规模问题中，寻找最优解是一件相当费时耗力的事情，有时候付出大量人力物力财力后，回报并不与投入成正比。在这个时候选择相对最优的贪心算法就比较经济可行了。有的问题对最优的要求不是很高，在充分衡量付出和回报后，选择贪心算法未尝不是一种不错的选择呢。

贪心算法求解时应该考虑的问题

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

例题会场安排

问题描述

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

输入要求

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

测试用例

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

算法思想

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

贪心选择性的证明

设C={1,2,…,n}是所给会议的集合，且按结束时间非减序排列。设C*是所给问题的一个最优解，且C*中会议的结束时间也按非减序排列，且C*中的第一个会议是k，若果k=1，，则C*就是一个以贪心选择的最优解。如果k>1,则设C‘=C*-K U 1。由于e₁<=e_k，且C*-k中的任何一个会议都为相容会议，它们的开始时间大于等于e_k，所以C*-k的开始时间大于等于e₁，所以C’中的会议也为相容会议，｜C’｜=｜C*｜，C*也是最优的。C‘是一个以贪心算法选择活动1开始的最优会议安排。

代码

#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;
        }
    } 
}