🪙 第3题：金币王国的兑换魔法
1、🌈 故事开场
在金币王国里，小明拿着一张“100元大金币”去换零钱 🪙
柜台上有这些硬币：
1元、5元、10元、20元、50元、100元国王说：
👉 “你必须用最少数量的硬币换出金额！”
2、❗ 问题
👉 给你一个钱数 n，最少要用多少枚硬币？
3、🧠 为什么是贪心？
（1）注意观察，硬币都是倍数>=2的关系
1张100元 = 2张50元
1张50元 = 2张20元+1张10元
1张20元 = 2张10元
1张10元 = 2张5元
1张5元 = 5张1元
（2）小明的策略是：
👉“每次都拿当前能用的最大硬币！”
比如要凑 137：
先拿 100（最大） ✅️
再看 50（ 不够拿）❌️
再拿 20 ✅️
再拿 10 ✅️
再拿 5 ✅️
再拿 1+1 ✅️
（3）👉 每一步都在做“当前最优选择”
这就是贪心！
4、❓ 为什么这样一定最优？
因为这个硬币系统有个特点：
👉“大面值是小面值的倍数结构”
例如：
10 = 5×2
20 = 10×2
👉 用大的，一定比用多个小的更省！
5、⚠️ 重要提醒
（1）不是所有零钱问题都能贪心！
比如：
硬币：1, 3, 4 凑6贪心：
4 + 1 + 1 = 3枚 ❌最优：
3 + 3 = 2枚 ✔（2）👉 所以：
⭐贪心规律成立是有条件的！
6、💻参考程序：
#include <iostream> using namespace std; int main() { int n; cin >> n; int coins[] = {100,50,20,10,5,1}; int ans = 0; for(int i = 0; i < 6; i++) { ans += n / coins[i]; n %= coins[i]; } cout << ans; }7、💻 代码详细讲解
int coins[] = {100,50,20,10,5,1};👉 按从大到小排列
for(int i = 0; i < 6; i++) { ans += n / coins[i]; n %= coins[i]; }🔍 每一步含义
第1步：
ans += n / coins[i];👉 能用多少个这种硬币？
例如：
137 / 100 = 1个第2步：
n %= coins[i];👉 剩下的钱继续处理
137 % 100 = 37🧠 整体流程
大 → 中 → 小 一层层剥掉8、🎯 本题本质
⭐ 每次“选择最大的”
🎒 第4题：背包精灵的收集任务
1、🌈 故事开场
小明有一个魔法背包 🎒，最多只能装W重量
森林里有很多宝物：
重量：5 3 8 2 12、❗ 任务
👉 小明想装最多数量的宝物！
（不是价值，是数量！）
3、🧠 为什么是贪心？
小明思考：
👉 “我应该先装轻的，还是重的？”
（1）❌ 如果先装重的
先装8 → 剩下很少空间👉 装不了几个 ❌
（2）✅ 如果先装轻的
1 → 2 → 3 → 5👉 可以装更多 ✔
（3）👉 所以策略：
⭐优先选最轻的！
4、🔍 实例推演
🎯 背包容量：W = 10
物品：
5 3 8 2 1🪜 第一步：排序
1 2 3 5 8🪜 第二步：开始装
👉 装1：
sum = 1 ✔👉 装2：
sum = 3 ✔👉 装3：
sum = 6 ✔👉 装5：
sum = 11 ❌ 超了！👉 停！
👉 最终装了：
1,2,3 → 共3个5、❓ 为什么这样最优？
因为：
👉 每次用最少空间，留下最多空间给后面
6、🎯 贪心规律总结
👉 每次选：
⭐当前最轻的物品
7、💻 参考代码
#include <iostream> #include <algorithm> using namespace std; int main() { int n, w; cin >> n >> w; int a[1005]; for(int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); int cnt = 0, sum = 0; for(int i = 0; i < n; i++) { if(sum + a[i] <= w) { sum += a[i]; cnt++; } } cout << cnt; }8、💻 代码详细讲解
（1）📦 排序
sort(a, a + n);👉 从小到大排列
（2）🎒 初始化
int cnt = 0, sum = 0;sum：当前重量
cnt：装了多少个
（3）🪜 遍历
for(int i = 0; i < n; i++) { if(sum + a[i] <= w) { sum += a[i]; cnt++; } }9、🔍 每一步含义
（1）判断：
sum + a[i] <= w👉 能不能装？
（2）如果能：
sum += a[i]; cnt++;👉 装进去！
（3）如果不能：
👉 跳过（因为后面更重，更不可能装）
10、🎯 本题本质
⭐每次选择是：“选择最小的”
🚀 两题对比
| 题目 | 策略 | 为什么 |
|---|---|---|
| 🪙 硬币 | 选最大 | 快速减少总量 |
| 🎒 背包 | 选最小 | 留出更多空间 |
🧠 总结：
第一题：🥇 “找钱尽可能找大面额的，才能最终张数少”
👉 选最大（硬币）
第二题：🥈 “装包尽量装小的，才能最终装的件数多”
👉 选最小（背包）
🎯 课后一句话
⭐贪心 = 每一步都做“最划算的选择”
但！
❗ 一定要验证：
👉局部最优 → 能不能变成整体最优！
