# 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     |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yunzhao.gitbook.io/notes/computer-science/algorithm/greedy-algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.