活动选择问题（活动安排问题）（最大数目活动选择问题）贪心算法C++实现

﹏ヽ暗。殇╰゛Y 2022-05-15 13:16 225阅读 0赞

// 活动选择问题（活动安排问题）（最大数目活动选择问题）.cpp : Defines the entry point for the console application.  
//贪心算法

\#include "stdafx.h"  
\#include<iostream>  
\#define N 100  
using namespace std;

struct Activity  
\{  
int number; //活动编号  
int begin; //活动开始时间  
int end; //活动结束时间  
bool flag; //此活动是否被选择  
\};  
//对于活动集，按照结束时间递增排序,使用快速排序  
void fast\_sort(Activity \*act,int f,int t)  
\{  
if(f<t)  
\{  
int i = f-1,j = f;  
Activity a = act\[t\];  
while(j<t)  
\{  
if(act\[j\].end<=a.end)  
\{  
i++;  
Activity temp1 = act\[i\];  
act\[i\] = act\[j\];  
act\[j\] = temp1;  
\}  
j++;  
\}  
Activity temp2 = act\[t\];  
act\[t\] = act\[i+1\];  
act\[i+1\] = temp2;  
fast\_sort(act,f,i);  
fast\_sort(act,i+2,t);  
\}  
\}  
//选择最大活动数目  
void select\_activity(Activity \*act,int n)  
\{  
int i = 0;  
act\[0\].flag = true;  
Activity a = act\[0\];  
for(i=1;i<n;i++)  
\{  
if(act\[i\].begin>=a.end)  
\{  
act\[i\].flag = true;  
a = act\[i\];  
\}  
\}  
\}

int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
int cases;  
Activity act\[N\];  
cout<<"请输入案例的个数："<<endl;  
cin>>cases;  
while(cases--)  
\{  
int n;  
cout<<"请输入活动的数目："<<endl;  
cin>>n;  
int i;  
for(i=0;i<n;i++)  
\{  
act\[i\].number = i+1;  
act\[i\].flag = false;  
cout<<"活动"<<i+1<<"开始时间：";  
cin>>act\[i\].begin;  
cout<<"活动"<<i+1<<"结束时间：";  
cin>>act\[i\].end;  
\}

//快速排序  
fast\_sort(act,0,n-1);

//选择最大数目活动集  
select\_activity(act,n);  
int sum = 0;  
cout<<"最终选择的活动集合为："<<endl;  
cout<<"< ";  
for(i=0;i<n;i++)  
if(act\[i\].flag)  
\{  
cout<<act\[i\].number<<" ";  
sum ++;  
\}  
cout<<">"<<endl;  
cout<<"最大活动集合的数目为："<<sum<<endl;  
\}  
system("pause");  
return 0;  
\}

\----------------------------------------------程序测试----------------------------------------------------

请输入案例的个数：  
1  
请输入活动的数目：  
11  
活动1开始时间：1  
活动1结束时间：4  
活动2开始时间：3  
活动2结束时间：5  
活动3开始时间：0  
活动3结束时间：6  
活动4开始时间：5  
活动4结束时间：7  
活动5开始时间：3  
活动5结束时间：8  
活动6开始时间：5  
活动6结束时间：9  
活动7开始时间：6  
活动7结束时间：10  
活动8开始时间：8  
活动8结束时间：11  
活动9开始时间：8  
活动9结束时间：12  
活动10开始时间：2  
活动10结束时间：13  
活动11开始时间：12  
活动11结束时间：14  
最终选择的活动集合为：  
<1 4 8 11 >  
最大活动集合的数目为：4  
请按任意键继续. . .