当前位置：首页 > news >正文

贪心算法简介（greed）

news 来源：原创 2025/8/17 12:53:08

前言：

贪心算法（Greedy Algorithm）是一种在每个决策阶段都选择当前最优解的算法策略，通过局部最优的累积来寻求全局最优解。其本质是"短视"策略，不回溯已做选择。

什么是贪心、如何来理解贪心(个人对贪心的理解)

前言对贪心是一种概念的回答。接下来就了解一下自己对贪心的理解，如果学习算法的化建议优先学习动态规划，动态规划相对于其他算法来说很简单。但是，贪心算法跟动态规划不同，非常难，贪心讲究策略，每一道贪心有每一道贪心题解题的策略。

什么是贪心算法：

解决问题的策略，由局部最优到全局最优，把解决问题的过程分为若干步，在解决每一步的时候，都选择当前看起来最优的解法，贪心就体现在最优上，希望得到全局最优，但只是看起来最优，在每一步的过程中都选择当前看起来最优的策略（找零问题），简单来说就是只考虑眼前的利益，目光不长远。

贪心算法的特点：

贪心策略的提出，可以看出贪心策略的提出是没有标准模板的，可能换一道贪心题其贪心策略也就不一样了，这也就是贪心难的地方了，可能每一道贪心题的贪心策略都是不同的。因为贪心是数目寸光的，所以就要考虑到贪心策略的正确性，有可能贪心策略是一个错误的方法，所以正确的贪心策略是需要严格证明的，说到贪心策略的证明，在数学上你见到的还是你没有见到的证明方法都可以拿来证明。

找零问题

#include <vector>
#include <algorithm>
using namespace std;vector<int> greedyCoinChange(int amount, vector<int> coins) {sort(coins.rbegin(), coins.rend()); // 降序排列vector<int> result;for (int coin : coins) {while (amount >= coin) {result.push_back(coin);amount -= coin;}}return (amount == 0) ? result : vector<int>(); // 返回空表示无解
}

活动选择

struct Activity {int start, end;
};vector<Activity> selectActivities(vector<Activity> activities) {sort(activities.begin(), activities.end(), [](const auto& a, const auto& b){ return a.end < b.end; });vector<Activity> selected;int lastEnd = -1;for (auto& act : activities) {if (act.start >= lastEnd) {selected.push_back(act);lastEnd = act.end;}}return selected;
}

前言：

什么是贪心、如何来理解贪心(个人对贪心的理解)

什么是贪心算法：

贪心算法的特点：

找零问题

活动选择

相关文章：