贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
具体代码如下所示：
#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++贪心算法实现活动安排问题，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对软件开发网网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！