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; }
相关推荐
Tips 2020-11-12
troysps 2020-08-18
Eduenth 2020-07-17
RememberMePlease 2020-06-26
yishujixiaoxiao 2020-06-16
Happyunlimited 2020-06-11
RememberMePlease 2020-06-07
从零开始 2020-05-31
路漫 2020-05-07
Happyunlimited 2020-05-01
从零开始 2020-04-30
ustbfym 2020-04-30
清溪算法 2020-04-22
baike 2020-04-15
pengkingli 2020-03-28
baike 2020-03-27
shawsun 2020-02-26
faiculty 2020-02-24
ipqtjmqj 2020-01-23