一、贪心算法的基本思想

所谓贪心算法是指，对问题求解时，总是做出在当前看来最好的选择。而不从整体最优加以考虑，得到的是局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析是否满足无后效性。贪心算法需要经过证明可行后，才可以运用到问题中。每一步的局部最优解，产生的全局解不一定是最优的，因此贪心法不需要回溯。

二、贪心算法设计基本思路

1. 建立数学模型来描述问题

2. 把求解的问题分解成若干个子问题

3. 对每一子问题求解，得到子问题的局部最优解

4. 把子问题的局部最优解合成原来问题的一个解

三、NP问题

集合覆盖问题、旅行商问题都属于NP完全问题，在数学领域并没有快速得到最优解的方案，贪心算法最适合处理这类问题。

如何判断是否是NP完全问题：

1. 元素较少时，运行速度很快，但随着元素数量增多，速度变得非常慢

2. 涉及到需要比较"所有组合"情况的通常是NP完全问题

3. 无法分割成小问题，必须考虑各种可能的情况，这可能是NP完全问题

4. 如果问题涉及序列（如旅行商问题中的城市序列），且难以解决，它可能就是NP完全问题

5. 如果问题涉及集合，且难以解决，它可能就是NP完全问题

6.如果问题可以转换成集合覆盖问题或者旅行商问题，那肯定是NP完全问题

四、贪心算法注意事项

1. 贪心算法解背包问题，不管选择什么策略，很难得到最优解

2. 当计算最优解，比如用穷举法，需求太长时间时，可以用贪心法中的近似算法计算近似最优解

3. 贪心算法得到可能是近似最优解，也可能就是最优解，比如区间调度问题，最短路径问题（广度优先、Dijkstra）

4.贪心算法（近似算法）大部分情况下易于实现，并且效率不错

五、实际场景

在一个教室安排最多课程问题、广播覆盖地区问题、货币支付问题、给更多的孩子分糖果问题

求最小生成树的Prim算法、Kruskal算法、计算强连通子图的Dijkstra算法、构造Huffman树的算法都是漂亮的贪心算法

六、贪心算法使用总结

不管是哪个场景使用贪心算法，都有一个共同点，那就是找到一个合理而贪心的策略，就行在一个教室中安排最多课程，需要从剩余课程集合中先找最先开始，最先结束的可能；在广播覆盖地区问题中，需要从剩余地区中找到覆盖最多地区的广播；货币支付问题中，先贪心的用最大面值货币；给更多孩子分糖果问题中，先用最小的糖，满足最小需求的孩子；

所以，判断在合适用贪心算法的场景，找到合适的策略，是用好贪心算法的关键。

注:文章最后图片拍摄于北京平谷区玻璃台村农家院。

谢谢大家可以添加关注或点赞，您的鼓励和支持是我们继续努力的最大动力！