贪心算法
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
具体代码如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#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++贪心算法实现活动安排问题,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对服务器之家网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!
原文链接:https://www.cnblogs.com/Jesse-Cavendish/archive/2019/11/04/11791036.html