贪心法（Greedy Algorithm）的核心思想就是：每次都选最好的！ 在每一步决策中，都选择当前看起来最优的选项，通过一系列局部最优的选择，最终达到全局最优。
贪心法适用于可通过局部最优解推出全局最优解的问题，通常具有以下特征：
需要注意的是，并非所有求最优解的问题都适合用贪心法。如果局部最优不能推出全局最优，则需要使用动态规划等其他方法。
使用贪心法解题的一般步骤：
以下排序算法都运用了贪心法的思想：
这些排序算法的共同点是：每一步都做出当前最优的选择（选最小的、交换错误的、插入正确位置），最终达到整体有序的目标。
问题： 用最少的硬币凑出 41 元，硬币面值有 25、10、5、1 元。
贪心策略： 每次优先使用面值最大的硬币。
| 步骤 | 剩余金额 | 贪心选择 | 使用硬币 | 原因 |
|---|---|---|---|---|
| 1 | 41 | 能用 25 吗？能 | 25元 x 1 | 41 >= 25，优先选最大面值 |
| 2 | 16 | 能用 25 吗？不能 | - | 16 < 25 |
| 3 | 16 | 能用 10 吗？能 | 10元 x 1 | 16 >= 10 |
| 4 | 6 | 能用 10 吗？不能 | - | 6 < 10 |
| 5 | 6 | 能用 5 吗？能 | 5元 x 1 | 6 >= 5 |
| 6 | 1 | 能用 5 吗？不能 | - | 1 < 5 |
| 7 | 1 | 能用 1 吗？能 | 1元 x 1 | 1 >= 1 |
| 8 | 0 | 结束 | - | 剩余为 0 |
结果： 使用 4 枚硬币（25+10+5+1），这确实是最优解。
问题： 硬币面值为 1、3、4 元，凑出 6 元。
这说明贪心法并不总是正确的！当硬币面值不满足特定条件时，贪心法可能得不到最优解，需要用动态规划。
例题：排队接水问题
有 n 个人排队接水，第 i 个人接水需要 t_i 分钟。如何安排顺序使得所有人的总等待时间最小？
解题步骤：
1// 按接水时间从小到大排序
2sort(t, t + n);
3int total_wait = 0;
4int current_wait = 0;
5for (int i = 0; i < n; ++i) {
6 total_wait += current_wait; // 第 i 个人的等待时间
7 current_wait += t[i]; // 更新累计时间
8}
9cout << total_wait << endl;