C++贪心算法实现活动安排问题(实例代码)

#include <cstdio>#include <iostream>#include <ctime>#include <windows.h>#include <algorithm>#include <fstream>using namespace std;struct activity{  int no;  int start;  int finish;};bool cmp(const activity &x, const activity &y){  return x.finish<y.finish;//从小到大排<，若要从大到小排则>}int greedySelector(int m,int solution[],struct activity activity[]){  int number = 1;  solution[0] = 1;  int i,j = 0,counter = 1;  for(i = 1;i < m ;i++)  {    if(activity[i].start >=activity[j].finish)    {      solution[i] = 1;      j = i;      counter++;    }    else      solution[i] = 0;  }  cout << "The amount of activities is:"<<counter<<endl;  cout << "The solution is:";  for(i = 0 ;i < m ;i++)  {    if (solution[i] == 1)    {      cout << activity[i].no <<" ";    }  }  return counter;}int main(void){  LARGE_INTEGER nFreq;  LARGE_INTEGER nBeginTime;  LARGE_INTEGER nEndTime;  ofstream fout;  srand((unsigned int)time(NULL));  int m,i,j,t;  double cost;  cout << "Please enter the number of times you want to run the program:";  cin >> t;  fout.open("activity.txt",ios::app);  if(!fout){    cerr<<"Can not open file 'activity.txt' "<<endl;    return -1;  }  fout.setf(ios_base::fixed,ios_base::floatfield);    //防止输出的数字使用科学计数法  for (j = 0;j < t;j++)  {    cout << "――――――――――――――――――The "<< j + 1 << "th test ―――――――――――――――――"<<endl;    m = 1 + rand()%100000;    fout<<m<<",";    int solution[m];    activity activity[m];    for( i = 0;i < m;i++)    {      activity[i].no = i+1;      activity[i].start = 1 + rand()%1000;      while(1)      {        activity[i].finish = 1 + rand()%10000;        if(activity[i].finish > activity[i].start) break;      }    }    QueryPerformanceFrequency(&nFreq);    QueryPerformanceCounter(&nBeginTime);    sort(activity,activity+m,cmp);    greedySelector(m,solution,activity);    QueryPerformanceCounter(&nEndTime);    cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;    fout << cost << endl;    cout << "/nThe running time is:" << cost << " s" << endl;  }  fout.close();  cout << endl << endl;  cout << "Success!" << endl;  return 0;}