贪心算法（C语言实现）

贪心算法是求最优解的一种常用方法，指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来完成。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。

贪心算法并不是对所有问题都能得到整体最优解，其关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

C语言贪心算法适用的问题：局部最优策略能产生全局最优解。但是实际上，贪心算法适用的情况很少。一般来说，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际实例进行分析，就可做出判断。

C语言贪心算法的一般步骤如下。

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的局部最优解合成原问题的一个解。

示例

问题描述：有 n 个活动都要求使用同一资源（如教室），资源在任何时刻只允许有一个活动使用。

每个活动 i 都有要求使用该资源的起始时间 si 终止时间 fi，并且 si<fi。也就是说，如果选择了活动 i，那么它在半开区间 [si，fi)内占用资源。

如何安排活动使尽可能多的活动能够充分地使用公共资源？

若区间 [si，fi) 与区间 [sj，fj) 不重叠，则称活动 i 与活动 j 相容，也就是说，当 sj≥fi 时，活动 i 与活动 j 相容。如此一来，活动安排问题就成了所给定活动集合中选出最大的相容活动子集。

C语言编程代码如下：

#include <stdio.h>
int main()
{
    int act[11] [3]={{1,1,4},{2,3,5},{3,0,6},{4,5,7},{5,3,8},{6,5,9},{7,6,10},{8,8,11},{9,8,12},{10,2,13},{11,12,14}};
    greedy(act,11);
    getch();
}
int greedy(int *act,int n)
{
    int i,j,no,start,minfinal,loop,sel[11];     /*sel[]用来存储相容的活动编号 */
    j=0;
    start=0;        /* 活动开始时间*/
    printf("活动安排：\n");
    while(1)
    {
        loop=0;        /* 循环是否终止的标记*/
        minfinal=24;    /* 记录每轮判断活动最早结束的时间*/
        no=0;            /* 记录符合条件的活动序号*/
        for(i=0;i<n;i++)
            if(act[i*3+1]>=start  && act[i*3+2]<minfinal)     
            {   minfinal=act[i*3+2];
                no=i;
                loop=1;
            }
        if(loop)
            sel[j]=no;
        else
            break;
        start=act[no*3+2];
        j++;
    }
    for(i=0;i<j;i++)
        printf("活动%2d:开始时间 %3d,结束时间 %3d\n",sel[i]+1,act[sel[i]*3+1],act[sel[i]*3+2]);
}

运行结果：

活动安排：
活动  1：开始时间    1，结束时间    4
活动  4：开始时间    5，结束时间    7
活动  8：开始时间    8，结束时间  11
活动11：开始时间  12，结束时间  14

本例利用贪心算法解决了活动安排的问题。

活动i	1	2	3	4	5	6	7	8	9	10	11
开始时间si	1	3	0	5	3	5	6	8	8	2	12
结束时间fi	4	5	6	7	8	9	10	11	12	13	14

如上表所示，将活动按结束时间的升序进行排列，并重新进行编号，然后进行如下的贪心选择过程：首先选取活动 1，然后依次检查活动 i 是否与当前已经选中的所有活动相容。如果相容，就加入已经选择的活动集合中；否则，继续检查下一个活动的相容性。

把会场要安排的所有活动作为一个集合 sel，初始开始时间标准为 start。

每次放入 sel 的活动要在满足“开始时间 s[i]>start 的前提下 f[i] 最小”。然后把 f[i] 赋值给 start 依次加入，直到加不进去为止。从而把问题解决。

由于活动是按结束时间的升序进行排列的，所以上述活动的过程总是选择具有最早完成时间的相容活动。它在直观上为未安排的活动留下了尽可能多的时间，也就是说，使剩余的可安排时间极大化，以便接待尽可能多的相容活动。

C语言贪心算法并不是针对任何一个问题都存在最优解，但是针对活动安排问题可以得到最优解。