Greedy Algorithm

介绍

贪心算法有很多经典应用，如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、Dijkstra 单源最短路径算法。

贪心算法思想：

1. 针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。

2. 当前情况下，每次选择在消耗同等限制值的情况下，对期望值贡献最大的数据；或者说对期望值贡献同等的情况下，消耗的限制值尽量少。

3. 举几个例子看下贪心算法产生的结果是否是最优的。严格证明贪心算法的正确性是非常复杂的。

用贪心算法解决问题的思路，并不总能给出最优解。尤其在前面的选择会影响后面的选择的情况下。

案例

• LeetCode 122：股票买卖最大利益。

背包问题

问题：一个背包可以容纳 100kg，有五种豆子，背包中应该装哪些豆子，每种豆子装多少，可以使背包中总价值最大。

物品	总量（kg）	总价值（元）
黄豆	100	100
绿豆	30	90
红豆	60	120
黑豆	20	80
青豆	50	75