贪心算法简介greed
目录
贪心算法简介（greed）
前言：
贪心算法（Greedy Algorithm）是一种在 每个决策阶段都选择当前最优解 的算法策略，通过 局部最优的累积来寻求全局最优解 。其本质是"短视"策略，不回溯已做选择。
什么是贪心、如何来理解贪心(个人对贪心的理解)
前言对贪心是一种概念的回答。接下来就了解一下自己对贪心的理解，如果学习算法的化 建议优先学习动态规划 ，动态规划相对于其他算法来说很简单。但是，贪心算法跟动态规划不同，非常难，贪心讲究策略， 每一道贪心有每一道贪心题解题的策略 。
什么是贪心算法：
解决问题的策略， 由局部最优到全局最优，把解决问题的过程分为若干步，在解决每一步的时候，都选择当前看起来最优的解法，贪心就体现在最优上，希望得到全局最优，但只是看起来最优，在每一步的过程中都选择当前看起来最优的策略 （找零问题），简单来说就是只考虑眼前的利益，目光不长远。
贪心算法的特点：
贪心策略的提出，可以看出贪心策略的提出是没有标准模板的，可能换一道贪心题其贪心策略也就不一样了，这也就是贪心难的地方了，可能每一道贪心题的贪心策略都是不同的。因为贪心是数目寸光的，所以就要考虑到 贪心策略的正确性 ， 有可能贪心策略是一个错误的方法，所以正确的贪心策略是需要严格证明的，说到贪心策略的证明，在数学上你见到的还是你没有见到的证明方法都可以拿来证明。
找零问题
#include
#include
using namespace std;
vector greedyCoinChange(int amount, vector coins) {
sort(coins.rbegin(), coins.rend()); // 降序排列
vector result;
for (int coin : coins) {
while (amount >= coin) {
result.push_back(coin);
amount -= coin;
}
}
return (amount == 0) ? result : vector(); // 返回空表示无解
}活动选择
struct Activity {
int start, end;
};
vector selectActivities(vector activities) {
sort(activities.begin(), activities.end(),
[](const auto& a, const auto& b){ return a.end < b.end; });
vector selected;
int lastEnd = -1;
for (auto& act : activities) {
if (act.start >= lastEnd) {
selected.push_back(act);
lastEnd = act.end;
}
}
return selected;
}