贪心算法c++代码实现 |21xrx.com

贪心算法c++代码实现

2023-07-04 05:03:09 深夜i 20 0

贪心算法 c++编程实现代码贪心思想

贪心算法是一种求解优化问题的方法，它通过每个子问题的最优解来寻求全局的最优解。与其他优化算法相比，贪心算法具有简单的实现、快速的计算速度和较好的近似效果。

在C++中，可以使用以下代码实现贪心算法：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 定义结构体
struct Task
  int start;
  int end;
;
// 比较函数
bool cmp(Task a, Task b)
  return a.end < b.end;
vector<Task> greedy_schedule(vector<Task>& tasks) {
  vector<Task> res;
  sort(tasks.begin(), tasks.end(), cmp);  // 先按照结束时间从小到大排序
  Task prev = tasks[0];
  res.push_back(prev);
  for (int i = 1; i < tasks.size(); i++) {
    if (tasks[i].start >= prev.end) {  // 如果当前任务的开始时间大于等于前一个任务的结束时间
      res.push_back(tasks[i]);
      prev = tasks[i];
    }
  }
  return res;
}
int main() {
  vector<Task> tasks = {1, 5, 0, 5, 8, 9, 10, 11, 8, 13, 14}; // 初始化任务
  vector<Task> res = greedy_schedule(tasks);
  for (int i = 0; i < res.size(); i++) {
    cout << "[" << res[i].start << ", " << res[i].end << "] ";
  }
  return 0;
}

我们以任务调度为例，假设有一堆任务，每个任务都有一个开始时间和结束时间。需要找出一种最优的方案能够完成尽可能多的任务。贪心算法可以很好地解决这个问题。

在实现代码中，我们首先定义了一个结构体Task，用于存储每个任务的开始时间和结束时间。同时，还定义了一个cmp比较函数，按照任务的结束时间从小到大排序，用于贪心选择最优解。

然后，我们采用vector容器存储任务，并且利用sort函数将任务按照cmp函数排序。接着，我们选取第一个任务并加入结果集合res中。之后，遍历每个任务，如果当前任务的开始时间大于等于前一个任务的结束时间，那么就将其加入结果集合中。最后返回结果集合即可。输出最优解的任务完成时间。

总之，贪心算法在实现上相对简单，但也存在局限性，只能得到近似最优解，因此需要根据具体问题实际应用。

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

下一篇: C++如何制作游戏？

评论区

相似文章