贪心算法有很多经典应用，如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、Dijkstra 单源最短路径算法。
贪心算法思想：
- 针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
- 当前情况下，每次选择在消耗同等限制值的情况下，对期望值贡献最大的数据；或者说对期望值贡献同等的情况下，消耗的限制值尽量少。
- 举几个例子看下贪心算法产生的结果是否是最优的。严格证明贪心算法的正确性是非常复杂的。
{% hint style="info" %} 用贪心算法解决问题的思路，并不总能给出最优解。尤其在前面的选择会影响后面的选择的情况下。 {% endhint %}
问题：一个背包可以容纳 100kg，有五种豆子，背包中应该装哪些豆子，每种豆子装多少，可以使背包中总价值最大。
| 物品 | 总量（kg） | 总价值（元） |
|---|---|---|
| 黄豆 | 100 | 100 |
| 绿豆 | 30 | 90 |
| 红豆 | 60 | 120 |
| 黑豆 | 20 | 80 |
| 青豆 | 50 | 75 |