什么是贪心算法？
贪心算法就像你在食堂打饭时，总是挑最好吃的菜先拿一样——每一步都选择当前看起来“最优”的方案，希望最后能得到全局最好的结果。它不一定每次都能拿到最完美的答案，但往往简单又高效，特别适合一些特定问题。
贪心算法的思路
- 面对一个问题：把大问题拆成一个个小选择。
- 每一步贪心：在当前情况下，选一个“局部最优”的答案。
- 拼起来：把这些小答案拼成最终结果。
一个经典例子：选硬币问题
问题描述
假设你有面值为 1 元、5 元、10 元、25 元的硬币，要凑出 36 元，怎么拿硬币数量最少？
贪心思路
- 每次都选最大的硬币，能用就用。
- 用完大的，再用小的，直到凑够为止。
解法步骤
- 36 ≥ 25，拿 1 个 25 元，还剩 36 – 25 = 11 元。
- 11 < 25，但 11 ≥ 10，拿 1 个 10 元，还剩 11 – 10 = 1 元。
- 1 < 10，但 1 ≥ 1，拿 1 个 1 元，还剩 1 – 1 = 0 元。
- 凑完了！用了 1 个 25 元 + 1 个 10 元 + 1 个 1 元 = 3 个硬币。
#include <iostream>
using namespace std;
int main() {
int coins[] = {25, 10, 5, 1}; // 硬币面值，从大到小
int n = 4; // 硬币种类数
int amount = 36; // 要凑的钱数
int count = 0; // 用了几枚硬币
cout << "需要凑的金额: " << amount << " 元" << endl;
// 贪心循环
for (int i = 0; i < n; i++) {
while (amount >= coins[i]) { // 当前面值还能用
amount -= coins[i]; // 减去这枚硬币
count++; // 硬币数加 1
cout << "用了 1 个 " << coins[i] << " 元的硬币，还剩 " << amount << " 元" << endl;
}
}
cout << "总共用了 " << count << " 枚硬币" << endl;
return 0;
}
输出结果
需要凑的金额: 36 元
用了 1 个 25 元的硬币，还剩 11 元
用了 1 个 10 元的硬币，还剩 1 元
用了 1 个 1 元的硬币，还剩 0 元
总共用了 3 枚硬币
代码解释
- coins[]：数组存硬币面值，从大到小排列，这样我们每次都先试最大的。
- while (amount >= coins[i])：只要剩下的钱还能用当前面值的硬币，就一直用。
- count：记录用了多少硬币。
什么时候用贪心算法？
贪心算法不适合所有问题，但像这种“每步选局部最优，最后也能全局最优”的情况很合适。比如：
- 凑硬币（某些情况）
- 安排活动（活动调度问题）
- 最短路径（Dijkstra 算法）
小练习
试试改一下代码，凑 67 元需要几枚硬币？自己跑跑看，结果是多少？
注意
贪心算法简单，但不一定总是对的。比如如果硬币面值是 {1, 4, 6}，要凑 8 元，贪心可能会出错（6+1+1=3枚），但其实 4+4=2 枚更好。所以奥赛里要多练，学会判断什么时候用贪心！
上机练习：
#P470. 【例85.3】 过河问题
#750. 【基础】修理牛棚 Barn Repair
ヾ(≧∇≦*)ゝ