贪心算法

💡 打个比方

商店找你 6 元钱，你手里有 1 元、3 元、4 元三种硬币。贪心的想法很简单：每次都拿手里最大的。

按贪心来：先拿 4 元 → 还差 2 元，只能拿 1 元 → 还差 1 元，再拿 1 元。一共 3 枚（4+1+1）。

可是等一下——如果先拿 3 元，还差 3 元，再拿一枚 3 元，2 枚就找完了（3+3）！"先拿最大的"这次反而吃亏了。

贪心就是每一步都选当前看起来最好的选择，不往前看全局。它简单、飞快，但不一定是最优解。什么时候能用贪心？看题目有没有最优子结构：大问题拆成小问题后，每个小问题各自做到最优，拼起来恰好就是整体最优——这时候贪心才敢用。

🖼️ 大图看明白

📏 怎么用贪心：只要 3 步

第 1 步：找出每一步的"局部最优"规则——拿最大的、选最近的、挑最便宜的。规则要一句话能说清楚，比如"每次拿不超过剩余金额的最大硬币"。

第 2 步：拿小例子验证！把规则手算一遍，再专门找反例（换个数字、换个面额再试）。像 4+1+1 vs 3+3 这样的反例一出现，贪心就不一定最优，得换方法。

第 3 步：写一个循环：每轮挑当前局部最优 → 更新剩下的问题 → 重复，直到问题清零。贪心不回头、不比较，所以特别快（找零只要 O(硬币种类×枚数) 次比较）。

💻 C++ 怎么写

// 贪心找零：每次拿不超过剩余金额的最大硬币
int coins[] = {50, 25, 10, 5, 1};  // 面额，从大到小
int money = 68, total = 0;         // 要找的钱、已用枚数
while (money > 0) {
    int pick = 1;                  // 兜底：1 元一定能拿
    for (int i = 0; i < 5; i++) {
        if (coins[i] <= money) {   // 找到最大的可用硬币
            pick = coins[i];
            break;                 // 面额从大到小，第一个就是最大
        }
    }
    money -= pick;                 // 更新剩余金额
    total++;                       // 枚数加 1
}
cout << total << endl;             // 输出 6（50+10+5+1+1+1）

✋ 你来试试