概念

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。

• 贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策略的选择，根据不同的问题选择不同的策略。

必须注意的是策略的选择必须具备无后效性，即某个状态的选择不会影响到之前的状态，只与当前状态有关，所以对采用的贪婪的策略一定要仔细分析其是否满足无后效性

基本思路：

1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。

适用性问题

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

框架

1
2
3
4
5
6

从问题的某一初始解出发；
    while （能朝给定总目标前进一步）
    { 
          利用可行的决策，求出可行解的一个解元素；
    }
    由所有解元素组合成问题的一个可行解；

例题

1. 分配饼干
2. 不重叠的区间个数
3. 投飞镖刺破气球
4. 根据身高和序号重组队列
5. 买卖股票最大的收益
6. 买卖股票的最大收益 II
7. 种植花朵
8. 判断是否为子序列
9. 修改一个数成为非递减数组
10. 子数组最大的和
11. 分隔字符串使同种字符出现在一起

https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E8%B4%AA%E5%BF%83%E6%80%9D%E6%83%B3.md

参考文章:

五大常用算法之三：贪心算法
贪心算法

FROM :blog.cfyqy.com | Author:cfyqy