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

骑猪看日落 2022-07-24 08:08 188阅读 0赞

**问题描述**：

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

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

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

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

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

在上述代码中，实现了递归方式的贪心算法和迭代方式的贪心算法，两者的时间复杂度都是O(n)。

**参考资料**：  
算法导论  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51439202  
作者：WSYW126