> For the complete documentation index, see [llms.txt](https://docs.1l.lol/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.1l.lol/algorithms/greedy.md).

# 贪心算法

### 思想

贪心算法在每一步都选择**当前看起来最优**的方案，希望最终得到全局最优。它不回溯、不后悔，效率高。

### 适用条件

* **贪心选择性质**：局部最优能推出全局最优
* **最优子结构**：问题的整体最优解包含子问题的最优解

不满足上述条件时，贪心可能得到错误答案（此时要用动态规划等）。

### 经典例子：活动选择

选择最多的互不重叠活动，按**结束时间**从小到大排序后贪心选取。

```cpp
sort(a, a + n, [](Node x, Node y){ return x.end < y.end; });
int cnt = 0, last = -1e9;
for (int i = 0; i < n; i++)
    if (a[i].start >= last) { cnt++; last = a[i].end; }
```

### 经典例子：找零 / 排队打水

* 找零：优先用大面额（面额需满足贪心条件）
* 排队打水：按打水时间**从小到大**排序，总等待时间最小

### 与动态规划的区别

|     | 贪心       | 动态规划       |
| --- | -------- | ---------- |
| 决策  | 只看当前，不回头 | 综合所有子问题    |
| 正确性 | 需证明      | 只要状态转移正确即可 |


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

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

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://docs.1l.lol/algorithms/greedy.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.

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.