贪心算法(Greedy Algorithm)，又可称作贪婪算法，简称贪心，它是一指一种决策策略，依据统一的规则，在局部选择最优解，继而成为全局最优解。最经典的问题就是一类最短路径问题，从当前节点选择离它最近的节点，然后继续，到达目标节点后这一路径就是全局最短路径（这是Dijkstra算法）；再如可分割的背包问题，物品有不同的重量和价值，但物品可分割，这也是贪心算法的经典应用案例。

贪心算法的适用范围

贪心算法最重要的特点是子问题的局部最优解即是最后的全局最优解，每一个子问题相互独立，不相互影响，这样的问题贪心能得到最优解，但通常这类问题较少，经典的就是会议室调度问题。

更多的时候，贪心是一近似算法（Approximation aglorithm），比如对于NP问题，贪心算法能得到一个近似解，虽然不是最优，但比较按近最优。比如像集合覆盖，地图着色，旅行商地图问题等，都是可以用贪心来求得一个近似解。

贪心算法就是，把问题分成多个子问题，设定一个贪心策略，针对每个子问题应用贪心策略，继而得到整个问题的解。比如会议室调度问题，每次都选择前一个会议结束后，最早开始最早结束；再如Dijkstra算法，每次从当前顶点出发，在其相邻的顶点中刷新较小的距离，并选择距离最短的顶点作为下一个当前顶点。

贪心与动态规划的区别

贪心和动态规划都是求解最优子结构问题，但贪心不考虑全局，只关注局部最优，而动态规划则要考虑整体最优解，局部可能选择最优也可能不选择。动态规划的应用范围更广，能用贪心解决的问题用动态规划一定可以，而能用动态规划解的，贪心不一定可以，应该说贪心是动态规划的一个子方法。

就比如0-1背包问题，如果物品不可分割，那么贪心是得不到解的，只考虑局部最优（每次选择最大能填满剩余空间的物品）是不可能得到全局最优解的，只能用动态规划来解。但假如物品是可以分割的，那么贪心就可解，并且是一个效率较高的解法。

典型题目

题目	题解	说明
121. 买卖股票的最佳时机	题解
1710. 卡车上的最大单元数	题解
2542. 最大子序列的分数	题解	反悔贪心
	题解
	题解
	题解

参考资料

• Greedy Algorithms
• Greedy Algorithms Explained with Examples
• Greedy Algorithm
• Greedy Algorithm with Example: What is, Method and Approach
• What is Greedy Algorithm: Example, Applications, Limitations and More
• Basics of Greedy Algorithms
• 贪心算法详解
• 小白带你学—贪心算法（Greedy Algorithm)
• 贪心算法详解（附例题）
• 五大基本算法之贪心算法 Greedy
• 贪心策略取得最优解的条件_常用算法之贪心算法
• 贪心算法