C++贪心算法实现活动安排问题

问题描述：

设有n个活动的集合E={1,2，…，n}，其中，每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间s_i和一个结束时间f_i，且s_i<f_i。如果选择了活动i，则它在半开时间区间[s_i,f_i)内占用资源。若区间[s_i,f_i)与区间[s_j,f_j)不相交，则称活动i与活动j是相容的。也就是说，当s_i≥f_­j或s_j≥f_i时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

细节须知：

暂无。

算法原理：

a.对活动进行排序

将各活动的起始时间和结束时间存储于数组中并按结束时间进行非减序排列，如果所给出的活动未按此序排列，可以进行重排。

b.依次向后寻找相容的且结束时间最早活动

算法开始选择活动1，并将j初始化为1。然后依次检查活动i是否与当前已选择的所有活动相容，若相容则将活动i加入已选择活动的集合A中；否则，不选择活动i，而继续检查下一活动与集合A中活动的相容性。由于f_j总是当前集合A中所有活动的最大结束时间，故活动i与当前集合A中所有活动相容的充分且必要的条件是其开始时间s_i不早于最近加入集合A的活动j的结束时间f_i。若活动i与之相容，则i成为最近加入集合A中的活动，并取代活动j的位置。由于输入的活动以其完成时间的非减序排列，所以算法每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <ctime>
 4 #include <windows.h>
 5 #include <algorithm>
 6 #include <fstream>
 7 using namespace std;
 8 struct activity
 9 {
10     int no;
11     int start;
12     int finish;
13 };
14 bool cmp(const activity &x, const activity &y)
15 {
16     return x.finish<y.finish;//从小到大排<，若要从大到小排则>
17 }
18 int greedySelector(int m,int solution[],struct activity activity[]){
19     int number = 1;
20     solution[0] = 1;
21     int i,j = 0,counter = 1;
22     for(i = 1;i < m ;i++)
23     {
24         if(activity[i].start >=activity[j].finish)
25         {
26             solution[i] = 1;
27             j = i;
28             counter++;
29         }
30         else
31             solution[i] = 0;
32     }
33     cout << "The amount of activities is:"<<counter<<endl;
34     cout << "The solution is:";
35     for(i = 0 ;i < m ;i++)
36     {
37        if (solution[i] == 1)
38        {
39             cout << activity[i].no <<" ";
40        }
41     }
42     return counter;
43 }
44 int main(void)
45 {
46     LARGE_INTEGER nFreq;
47     LARGE_INTEGER nBeginTime;
48     LARGE_INTEGER nEndTime;
49     ofstream fout;
50     srand((unsigned int)time(NULL));
51     int m,i,j,t;
52     double cost;
53     cout << "Please enter the number of times you want to run the program:";
54     cin >> t;
55     fout.open("activity.txt",ios::app);
56     if(!fout){
57         cerr<<"Can not open file 'activity.txt' "<<endl;
58         return -1;
59     }
60     fout.setf(ios_base::fixed,ios_base::floatfield);       //防止输出的数字使用科学计数法
61     for (j = 0;j < t;j++)
62     {
63         cout << "——————————————————The "<< j + 1 << "th test —————————————————"<<endl;
64         m = 1 + rand()%100000;
65         fout<<m<<",";
66         int solution[m];
67         activity activity[m];
68         for( i = 0;i < m;i++)
69         {
70             activity[i].no = i+1;
71             activity[i].start = 1 + rand()%1000;
72             while(1)
73             {
74                 activity[i].finish = 1 + rand()%10000;
75                 if(activity[i].finish > activity[i].start) break;
76             }
77         }
78         QueryPerformanceFrequency(&nFreq);
79         QueryPerformanceCounter(&nBeginTime);
80         sort(activity,activity+m,cmp);
81         greedySelector(m,solution,activity);
82         QueryPerformanceCounter(&nEndTime);
83         cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;
84         fout << cost << endl;
85         cout << "\nThe running time is:" << cost << " s" << endl;
86     }
87     fout.close();
88     cout << endl << endl;
89     cout << "Success!" << endl;
90     return 0;
91 }

程序设计思路：

① 数据结构：结构体中存储活动序号、活动开始时间、活动结束时间；

② 利用C++自带的sort函数对结构体按照活动结束时间进行升序排列；

③ 算法开始选择活动1，并将j初始化为1。然后依次检查活动i是否与当前已选择的所有活动相容，若相容则将活动i加入已选择活动的集合A中；否则，不选择活动i，而继续检查下一活动与集合A中活动的相容性。由于f_j总是当前集合A中所有活动的最大结束时间，故活动i与当前集合A中所有活动相容的充分且必要的条件是其开始时间s_i不早于最近加入集合A的活动j的结束时间f_i。若活动i与之相容，则i成为最近加入集合A中的活动，并取代活动j的位置。由于输入的活动以其完成时间的非减序排列，所以算法每次总是选择具有最早完成时间的相容活动加入集合A中。

时间复杂性分析：

首先，需要对输入的事件按照结束时间进行非减序排列，需要用O（nlogn）的时间。其次，算法greedySelector的效率极高，当输入的活动已按结束时间的非减序排列，算法只需θ（n）的时间安排n个活动，使最多的活动能相容地使用公共资源。

生成的数据可导入EXCEL中进行数据分析生成分析图表。