贪心算法简介（greed）

媒介：

贪心算法（Greedy Algorithm）是一种在每个决策阶段都选择当前最优解的算法策略，通过局部最优的累积来寻责备局最优解。其本质是"短视"策略，不回溯已做选择。
什么是贪心、如何来明白贪心(个人对贪心的明白)

媒介对贪心是一种概念的答复。接下来就相识一下自己对贪心的明白，如果学习算法的化建议优先学习动态规划，动态规划相对于其他算法来说很简朴。但是，贪心算法跟动态规划差别，非常难，贪心讲究策略，每一道贪心有每一道贪心题解题的策略。
什么是贪心算法：

解决题目的策略，由局部最优到全局最优，把解决题目的过程分为若干步，在解决每一步的时候，都选择当前看起来最优的解法，贪心就体如今最优上，盼望得到全局最优，但只是看起来最优，在每一步的过程中都选择当前看起来最优的策略（找零题目），简朴来说就是只思量眼前的长处，眼光不长远。
贪心算法的特点：

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

1. #include <vector>
2. #include <algorithm>
3. using namespace std;
5. vector<int> greedyCoinChange(int amount, vector<int> coins) {
6.     sort(coins.rbegin(), coins.rend()); // 降序排列
7.     vector<int> result;
8.    
9.     for (int coin : coins) {
10.         while (amount >= coin) {
11.             result.push_back(coin);
12.             amount -= coin;
13.         }
14.     }
15.    
16.     return (amount == 0) ? result : vector<int>(); // 返回空表示无解
17. }

复制代码

运动选择

1. struct Activity {
2.     int start, end;
3. };
5. vector<Activity> selectActivities(vector<Activity> activities) {
6.     sort(activities.begin(), activities.end(),
7.         [](const auto& a, const auto& b){ return a.end < b.end; });
8.    
9.     vector<Activity> selected;
10.     int lastEnd = -1;
11.    
12.     for (auto& act : activities) {
13.         if (act.start >= lastEnd) {
14.             selected.push_back(act);
15.             lastEnd = act.end;
16.         }
17.     }
18.    
19.     return selected;
20. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。