服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++贪心算法实现活动安排问题(实例代码)

C++贪心算法实现活动安排问题(实例代码)

2021-08-05 11:55Weisswire C/C++

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。这篇文章主要介绍了C++贪心算法实现活动安排问题,需要的朋友可以参考下

贪心算法

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

具体代码如下所示:

?
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

延伸 · 阅读

精彩推荐