21xrx.com
2024-11-09 00:16:08 Saturday
登录
文章检索 我的文章 写文章
贪心算法c++代码实现
2023-07-04 05:03:09 深夜i     --     --
贪心算法 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中。之后,遍历每个任务,如果当前任务的开始时间大于等于前一个任务的结束时间,那么就将其加入结果集合中。最后返回结果集合即可。输出最优解的任务完成时间。

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

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复