贪心算法：每一步都选最好的，真的能赢吗？

你是否遇过这样的场景：面前有一堆糖果，你每次都伸手去拿最大的那一块，最后觉得自己吃得最多？这种“每一步都选当前看起来最好”的做法，就是 贪心算法 的核心思想。贪心算法（Greedy Algorithm）是一种简单直接的解题策略：在解决问题的每一步，都选择当前看来最有利的选择，而不考虑这个选择会不会影响后面的步骤。它就像你吃自助餐时，先拿最贵的海鲜，而不是先喝汤填饱肚子——你觉得海鲜最划算，就先吃它。很多实际问题（比如找零、排课、背包打包）都能用贪心快速搞定，但贪心不一定永远正确——有时你拿了最大的糖，却错过了藏在下面的巧克力。

贪心的核心思想：局部最优，期望全局最优

贪心算法的本质是“短视”：只看眼前，不管未来。它假设每一步的最优选择能堆出整体的最优解。比如你去超市买零食，手里的钱只够买三样东西，你每次都挑最想吃的那个，最终组合可能就是你觉得最满意的。但在数学上，这种“局部最优加起来等于全局最优”不是天然成立的，需要问题本身有特殊性质。

生活中的贪心例子

拿糖果：一堆糖果中，每次都拿最大的，最后你拿的总重量不一定最大，但如果你拿的是巧克力（每颗大小不同但价值相同），那贪心就对了。
排队买冰淇淋：看到好几条队伍，你选了最短的那条排队。这是贪心——你希望最快买到，但万一短队伍后面来了很多人，而长队伍反而更快呢？不过大多数时候，选最短队是合理的。
人民币找零：比如要找63元，你会先给一张50元，再给一张10元，最后给3个1元。每次都用最大面额，最终硬币张数最少。这是因为人民币的面额（1、5、10、20、50、100）是特制的，让贪心有效。
安排周末活动：你有好几个想看的电影，每个电影有开始和结束时间，如何选最多的电影？贪心策略是：每次选结束时间最早的那个，然后跳过所有冲突的电影。这样你就能看尽可能多的电影。

贪心不一定总是对的——举个反例

假设你有一堆奇怪的硬币，面额分别为1元、3元、4元。现在要找你6元钱。如果用贪心先拿最大的4元，剩下2元，只能再拿两个1元，总共3枚硬币。但最优解是拿两个3元，只用2枚硬币！所以贪心在这里失败了。这就是为什么使用贪心前必须确认问题是否适合“每次选最好的”。

什么时候贪心有效？——两个关键性质

要让贪心算法保证得到全局最优解，问题一般需要满足两个性质（你不必背定义，但理解它们有助于判断）：

最优子结构：一个问题的最优解，包含它的子问题的最优解。比如找零，如果全局最少硬币数是6，那么去掉一个硬币后，剩下的金额也应该能用最少的硬币数。
贪心选择性质：每一步的局部最优选择，最终能成为全局最优解的一部分。在找零中，每次都选最大面额，正好符合这个性质（前提是面额设计合理）。

典型应用一：硬币找零问题（保留原内容）

下面这个例子来自生活：你有1元、5元、10元、25元硬币，需要找零63元，如何用最少的硬币？贪心做法是每次都选不超过剩余金额的最大硬币：

#include <iostream>
#include <vector>
using namespace std;

// 硬币面额，从大到小排序，确保每次先取最大
vector<int> coins = {25, 10, 5, 1};

int greedyChange(int amount) {  // 参数：要找零的金额
    int count = 0;              // 记录硬币总数
    for (int coin : coins) {    // 从大到小遍历每一面额
        // 尽可能多用当前最大面额
        int num = amount / coin;   // 计算可以用多少枚这种硬币
        count += num;               // 累加硬币数
        amount -= num * coin;       // 更新剩余金额
    }
    return count;
}

int main() {
    int amount = 63;
    int coinsUsed = greedyChange(amount);
    cout << "找零 " << amount << " 元需要 " << coinsUsed << " 枚硬币" << endl;
    // 输出：找零 63 元需要 6 枚硬币（2个25元+1个10元+3个1元）
    return 0;
}

这段代码简单易懂，但请记住它只在硬币面额为“正常”时有效。如果换成上面反例中的1、3、4元，它就会出错。

典型应用二：活动安排问题（选最多课程）

作为中学生，你一定选过课外兴趣班，或者看过电影排片表。假设你有一堆活动，每个活动有开始时间和结束时间，你想一口气参加尽可能多的活动，但同一时间只能参加一个。贪心策略很简单：每次选结束时间最早的那个活动，然后放弃所有与它冲突的活动，重复下去。

举一个具体的例子：活动列表如下（为了方便，用整数表示时间，比如9:00就是9）：

活动	开始时间	结束时间
体育	8	10
音乐	9	11
美术	10	12
编程	11	13

按照贪心，先选结束时间最早的——体育（8-10）。然后所有开始时间早于10（体育结束）的活动都不能选，所以音乐（9-11）被跳过，因为它在体育结束前就开始了。下一个可选的是美术（10-12），选上。然后编程（11-13）开始时间11小于美术结束时间12，冲突，跳过。最终只选了体育和美术，共2个活动。实际上，最优解也是2个（比如音乐和编程，或体育和美术），贪心成功。

下面给出完整代码：

#include <iostream>
#include <vector>
#include <algorithm>  // 用于 sort 排序
using namespace std;

struct Activity {
    int start;   // 开始时间
    int finish;  // 结束时间
};

// 按结束时间从小到大排序的比较函数
bool compareByFinish(Activity a, Activity b) {
    return a.finish < b.finish;
}

int greedyActivities(vector<Activity> &act) {
    // 1. 先按结束时间排序
    sort(act.begin(), act.end(), compareByFinish);
    
    int count = 0;           // 选中的活动数量
    int lastFinish = -1;     // 上一个选中活动的结束时间，初始为最小
    
    for (int i = 0; i < act.size(); i++) {
        // 2. 如果当前活动开始时间 >= 上一个结束时间，就可以选
        if (act[i].start >= lastFinish) {
            count++;
            lastFinish = act[i].finish;  // 更新最后结束时间
            cout << "选中活动：开始=" << act[i].start 
                 << ", 结束=" << act[i].finish << endl;
        }
    }
    return count;
}

int main() {
    // 创建活动列表，包含开始和结束时间
    vector<Activity> activities = {
        {8, 10},   // 体育
        {9, 11},   // 音乐
        {10, 12},  // 美术
        {11, 13}   // 编程
    };
    
    cout << "最多能参加 " << greedyActivities(activities) << " 个活动" << endl;
    return 0;
}

运行输出：

选中活动：开始=8, 结束=10
选中活动：开始=10, 结束=12
最多能参加 2 个活动

这个例子非常贴近学生的日常：选课、社团活动、看电影排片——都可以用贪心快速找到最多场次。

新手常犯的错误

没有排序就贪心：在活动安排中，如果不按结束时间排序，直接遍历，就可能先选了一个很长的活动，导致后面很多活动冲突。贪心前常常需要排序或预处理。
拿起来就用，不验证正确性：看到问题就套贪心，结果遇到反例（比如奇怪的硬币）就错了。在考试或比赛中，如果时间允许，最好先尝试构造一个反例来测试贪心是否有效。
误解“当前最优”：比如找零时，有的人可能会先拿最多数量的硬币（比如1元），但那不是贪心（贪心要“最大面额”）。一定要明确“最优”的标准是什么。
忘记更新状态：在循环里，只顾着取最大，却忘了更新剩余金额或剩余资源。比如上面的硬币找零代码中，amount -= num * coin 这一步不能漏掉。

完整可运行代码示例（整合硬币找零和活动安排）

下面给你一个完整的程序，包含两个贪心应用，直接复制到DEV‑C++或在线编译器就能跑：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// ========== 硬币找零（贪心） ==========
int coinChange(int amount, vector<int> coins) {
    // coins 已从大到小排序
    int count = 0;
    for (int coin : coins) {
        int num = amount / coin;   // 用当前面额硬币的个数
        count += num;
        amount -= num * coin;       // 减去已用掉的金额
    }
    return count;
}

// ========== 活动安排（贪心） ==========
struct Activity {
    int start;
    int finish;
};
bool cmpFinish(Activity a, Activity b) {
    return a.finish < b.finish;   // 按结束时间升序
}
int maxActivities(vector<Activity> &acts) {
    sort(acts.begin(), acts.end(), cmpFinish);
    int count = 0;
    int lastEnd = -1;
    for (auto &act : acts) {
        if (act.start >= lastEnd) {
            count++;
            lastEnd = act.finish;
        }
    }
    return count;
}

int main() {
    // 1. 硬币找零演示
    cout << "===== 硬币找零 =====" << endl;
    vector<int> coins = {25, 10, 5, 1};
    int money = 63;
    int coinsNeeded = coinChange(money, coins);
    cout << "找零 " << money << " 元，最少需要 " << coinsNeeded << " 枚硬币" << endl;

    // 2. 活动安排演示
    cout << "\n===== 活动安排 =====" << endl;
    vector<Activity> activities = {
        {8, 10},
        {9, 11},
        {10, 12},
        {11, 13}
    };
    int actCount = maxActivities(activities);
    cout << "最多能参加 " << actCount << " 个活动" << endl;

    return 0;
}

输出结果：

===== 硬币找零 =====
找零 63 元，最少需要 6 枚硬币

===== 活动安排 =====
最多能参加 2 个活动

总结与相关指引

贪心算法是一种“短视但高效”的技巧：速度快、代码短，但只适用于特定问题。你可以在以下场景大胆尝试贪心：

找零问题（面额合理）
活动安排（选最多不冲突的活动）
哈夫曼编码（数据压缩）
单源最短路径的Dijkstra算法（本质也是贪心）

如果一个问题不满足贪心性质，就需要考虑其他算法，比如动态规划（从小的子问题一步步构造最优解）或回溯法（暴力试所有可能性）。你可以进一步学习：

动态规划入门：当贪心失效时，动态规划能通过记忆化搜索或递推得到正确结果。
分治算法：把大问题拆成小问题分别解决，与贪心不同，分治会合并子问题的解。

记住：贪心之前，先问问自己——这次拿最大的，真的能一直赢到最后吗？ 如果拿不准，可以用小数据试一下，或者尝试构造一个反例。掌握了贪心的思想，你就能在面对很多生活问题时快速找到不错的方案，甚至是最优解！

贪心算法思想：每次选最好的，然后呢？