# Greedy Algorithm

## 介绍

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

贪心算法思想：

1. 针对一组数据，我们定义了**限制值**和**期望值**，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
2. 当前情况下，每次选择在消耗同等限制值的情况下，对期望值贡献最大的数据；或者说对期望值贡献同等的情况下，消耗的限制值尽量少。
3. 举几个例子看下贪心算法产生的结果是否是最优的。严格证明贪心算法的正确性是非常复杂的。

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

## 案例

* [LeetCode 122：股票买卖最大利益。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/greedy/LT122.java)

### 背包问题

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

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