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

总结

以上所述是小编给大家介绍的C++贪心算法实现活动安排问题，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对<计算机技术网(www.ctvol.com)!!>网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！

—-想了解C++贪心算法实现活动安排问题(实例代码)分享！全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>