C++贪心算法经典例题 |21xrx.com

C++贪心算法经典例题

2023-07-06 00:12:54 深夜i 12 0

C++ 贪心算法经典例题算法优化最小生成树

C++贪心算法是算法分析中的一种方法，用于解决一些最优化问题。它的主要思想是在每一步选择中都采取在当前状态下最好或最优的选择，从而希望最后得到全局最好或最优的解。下面我们来看一下贪心算法的一个经典例题。

假设我们有n个活动，每个活动都有一个开始时间s[i]和结束时间f[i]。例如，我们有以下6个活动：

活动编号 1 2 3 4 5 6 开始时间 1 3 0 5 8 5 结束时间 4 5 6 7 9 9

如果两个活动在同一时间结束，我们可以同时安排它们。我们的目标是在给定的时间内尽可能地安排更多的活动。

贪心算法的思路是首先按照结束时间将所有的活动排序，然后从第一个活动开始，如果下一个活动的开始时间晚于当前活动的结束时间，就可以安排这个活动，然后将当前活动设置为下一个可以安排的活动。重复这一过程直到没有可以安排的活动为止。

以下是使用C++语言实现这个算法的代码：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Activity
  int start;
  int finish;
;
bool compare(const Activity& a1, const Activity& a2)
  return a1.finish < a2.finish;
vector<int> selectActivities(vector<Activity> activities) {
  sort(activities.begin(), activities.end(), compare);
  vector<int> solution;
  int last_finish_time = -1;
  for (int i = 0; i < activities.size(); i++) {
    if (activities[i].start >= last_finish_time) {
      solution.push_back(i);
      last_finish_time = activities[i].finish;
    }
  }
  return solution;
}
int main() {
  vector<Activity> activities = {
     4, 5, 6, 5, 8, 9  
  };
  vector<int> solution = selectActivities(activities);
  cout << "Activities to select: ";
  for (int i = 0; i < solution.size(); i++) {
    cout << solution[i] + 1 << " ";
  }
}

输出结果如下所示：

Activities to select: 1 2 4 5

通过使用C++贪心算法，我们成功地找到了最优解，选择了4个活动，它们的编号分别是1, 2, 4和5。

总之，贪心算法是一种简单但非常有效的最优化算法，并且具有广泛的应用领域。这个例题就可以帮助我们深入了解贪心算法的思想和实现方式。

上一篇: idea打包java可执行jar包

下一篇: C++实现大写字母转小写字母的程序

评论区

相似文章