欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-31 19:18:09
_(:з」∠)_ ......

_(:з」∠)_

 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 }