硬币找零问题 - 贪心算法 C++ 教程

什么是硬币找零问题？

硬币找零问题是这样一个问题：给定一个金额，使用最少数量的硬币来凑出这个金额。假设我们有不同面值的硬币。

什么是贪心算法？

贪心算法是一种在每一步选择中都采取当前状态下最优的选择，希望通过局部最优解达到全局最优解的算法策略。

在硬币找零问题中，贪心算法的思路是：每次选择面值尽可能大的硬币，直到凑够所需的金额。

⚠️ 注意：贪心算法并不总能得到最优解。它能成功取决于硬币的面值设计。比如人民币、美元等常见货币体系可以使用贪心算法得到最优解。

举个例子

假设我们要找 63 元的零钱，可选的硬币面值为：50元、20元、10元、5元、1元

按照贪心算法：

• 选择1张50元（剩下13元）
• 选择1张10元（剩下3元）
• 选择3张1元

总共用了5张纸币/硬币

C++ 实现代码（带详细注释）

#include <iostream>
#include <vector>

using namespace std;

// 函数：计算最少需要多少个硬币来找零
int coinChange(int amount, vector<int>& coins) {
    // 先按从大到小的顺序排序硬币面值
    sort(coins.begin(), coins.end(), greater<int>());
    
    int count = 0;  // 记录使用的硬币数量
    
    // 遍历所有面值
    for (int coin : coins) {
        // 计算当前面值的硬币最多能用多少个
        int num = amount / coin;
        
        // 如果能用到这个面值的硬币
        if (num > 0) {
            cout << "使用" << num << "个" << coin << "元硬币/纸币" << endl;
            count += num;           // 增加计数
            amount -= num * coin;   // 减去已找的金额
        }
        
        // 如果已经找完零钱，就退出循环
        if (amount == 0) {
            break;
        }
    }
    
    // 返回使用的硬币数量
    return count;
}

int main() {
    // 定义可用的硬币面值（这里以人民币为例）
    vector<int> coins = {1, 5, 10, 20, 50};
    
    // 要找的零钱金额
    int amount;
    cout << "请输入要找零的金额：";
    cin >> amount;
    
    // 计算并输出结果
    int result = coinChange(amount, coins);
    cout << "最少需要" << result << "个硬币来找零" << endl;
    
    return 0;
}

代码解释（适合中小学生理解）

让我们一步一步地来看这段程序：

第一部分：引入头文件和命名空间

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

• #include 是把一些已有的功能导入我们的程序
• iostream 让我们可以使用输入输出功能（比如显示文字、读取键盘输入）
• vector 是一种数据结构，可以存储多个数值
• algorithm 包含排序等功能
• using namespace std; 是为了方便写代码，告诉电脑我们使用标准名称空间

第二部分：主函数

int main() {
    // 定义可用的硬币面值（这里以人民币为例）
    vector<int> coins = {1, 5, 10, 20, 50};
    
    // 要找的零钱金额
    int amount;
    cout << "请输入要找零的金额：";
    cin >> amount;
    
    // 计算并输出结果
    int result = coinChange(amount, coins);
    cout << "最少需要" << result << "个硬币来找零" << endl;
    
    return 0;
}

• 我们先定义了有哪些面值的硬币可以使用
• 然后让用户输入想要找零的金额
• 接着调用我们写的找零函数
• 最后显示最少需要多少个硬币

第三部分：找零函数

int coinChange(int amount, vector<int>& coins) {
    // 先按从大到小的顺序排序硬币面值
    sort(coins.begin(), coins.end(), greater<int>());
    
    int count = 0;  // 记录使用的硬币数量
    
    // 遍历所有面值
    for (int coin : coins) {
        // 计算当前面值的硬币最多能用多少个
        int num = amount / coin;
        
        // 如果能用到这个面值的硬币
        if (num > 0) {
            cout << "使用" << num << "个" << coin << "元硬币/纸币" << endl;
            count += num;           // 增加计数
            amount -= num * coin;   // 减去已找的金额
        }
        
        // 如果已经找完零钱，就退出循环
        if (amount == 0) {
            break;
        }
    }
    
    // 返回使用的硬币数量
    return count;
}

• 首先将硬币按面值从大到小排序
• 然后依次尝试每种面值的硬币：
  • 看看当前金额里有几个这种面值的硬币
  • 如果有，就记录下来用了几个
  • 然后减去这部分金额
• 直到金额减到0为止

小学生也能理解的例子

想象你有一堆不同大小的积木，你要搭一个高度正好是10厘米的塔：

• 有5厘米高的大积木
• 有2厘米高的中等积木
• 有1厘米高的小积木

你想用最少的积木块数来搭成10厘米高

按照贪心思想：

1. 先尽可能多地用最大的积木（5厘米）→ 用2块刚好够10厘米
2. 这样只用了2块积木，是最少的可能

这就是贪心算法的思想！

练习建议

1. 尝试修改硬币的面值，看看程序还能不能正确工作
2. 添加更多面值的硬币，如100元、5角、1角
3. 修改程序，让它输出具体的找零方案而只是硬币数量

希望这个教程对初学者理解贪心算法和硬币找零问题有所帮助！