算法导论之贪心算法：活动选择问题-蒲公英云

算法导论之贪心算法：活动选择问题

问题描述：

每个活动都共享同一个公共的资源（比如教室等）所以同一时间只能有一个活动。现在的问题就是要在指定的时间内让举办的活动数量做大。

这是一个典型的贪心算法。我们不在这里证明算法的正确性。

我们给出贪心算法的定义：它在每一步都作出当时看起来最佳的选择。（它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解）

一般的贪心算法有以下的步骤：

1.确定问题的最优子结构。

2.设计一个递归算法。

3.证明如果我们做出一个贪心选择，则只剩下一个子问题。

4.证明贪心选择总是安全的。（步骤3、4的顺序可以调换）

5.设计一个递归算法实现贪心策略。

6.将递归算法转换为迭代算法。

代码实现如下：

#include <stdio.h>
struct Activty{
    int start;
    int finish; 
};
typedef struct Activty Activty;
struct List{
    Activty *value;
    struct List *next; 
};
typedef struct List List;
//迭代贪心算法 
List *GREEDY_ACTIVITY_SELECTOR(Activty action[],int n){
    List *rs = (List *)malloc(sizeof(List));
    rs->value=action;
    List *position = rs;
    int k=0,m=1;
    for(;m<n;m++){
        if(action[m].start>=action[k].finish){
            List *temp = (List *)malloc(sizeof(List));
            temp->value=&action[m];
            position->next=temp;
            position=temp;
            k=m;
        }
    }
    position->next=NULL;
    return rs;
}
//递归贪心算法 
List *RECURSIVE_SELECTOR(Activty action[],int k,int n){
    int m = k+1;
    while(m<n && action[m].start<action[k].finish){
        m++;
    }
    if(m<n){
        List *rs = (List *)malloc(sizeof(List));
        rs->value=&action[m];
        rs->next=RECURSIVE_SELECTOR(action,m,n);
        return rs;
    }else
        return NULL;
}
int main(int argc, char *argv[])
{
    int n = 11;
    Activty action[n];
    //下面是测试数据
    action[0].start=1;action[0].finish=4;
    action[1].start=3;action[1].finish=5;
    action[2].start=0;action[2].finish=6;
    action[3].start=5;action[3].finish=7;
    action[4].start=3;action[4].finish=9;
    action[5].start=5;action[5].finish=9;
    action[6].start=6;action[6].finish=10;
    action[7].start=8;action[7].finish=11;
    action[8].start=8;action[8].finish=12;
    action[9].start=2;action[9].finish=14;
    action[10].start=12;action[10].finish=16;
    List *rs = (List *)malloc(sizeof(List));
    rs->value=&action[0];
    rs->next= RECURSIVE_SELECTOR(action,0,n);
    List *temp = rs;
    printf("the follow is RECURSIVE_SELECTOR.\n");
    while(temp!=NULL){
        printf("%d,%d\n",temp->value->start,temp->value->finish);
        temp=temp->next;
    }
    List *rs_GREEDY=GREEDY_ACTIVITY_SELECTOR(action,n);
    temp = rs_GREEDY;
    printf("\nthe follow is GREEDY_ACTIVITY_SELECTOR.\n");
    while(temp!=NULL){
        printf("%d,%d\n",temp->value->start,temp->value->finish);
        temp=temp->next;
    }
    return 0;
}