C++贪心算法实现活动安排问题(实例代码)
更新时间:2020年4月25日 17:24 点击:1447
贪心算法
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
具体代码如下所示:
#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++贪心算法实现活动安排问题,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对猪先飞网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!
上一篇: C语言实现经典24点纸牌益智游戏
下一篇: C++实现推箱子游戏
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25