贪心算法解决钱币找零问题(二)

问题描述

钱币找零问题是算法领域的经典问题，具体描述为：给定一定金额和一组不同面额的钱币，如何使用最少数量的钱币组合出该金额？本文将使用贪心算法解决这一问题，并通过代码实现展示其具体应用。

例如：

• 输入：面额 [25, 10, 5, 1]，金额 41
• 输出：总张数 4，各面额使用数量 1 1 1 1（即 25+10+5+1=41）

贪心算法的适用场景

贪心算法通过 "每次选择局部最优解" 来寻求全局最优解，适用于具有 "贪心选择性质" 的问题。对于钱币找零问题：

• 当钱币系统满足 "较大面额是较小面额的倍数" 时（如人民币、美元等十进制货币），贪心算法可得到最优解
• 典型反例：面额 [1, 3, 4] 找零 6，贪心会选择 4+1+1（3 张），但最优解是 3+3（2 张）

本文实现基于满足贪心选择性质的钱币系统。

代码实现与解析

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;/*** 钱币找零函数（贪心算法）* @param amount 需要找零的金额* @param denominations 钱币面额数组* 输出格式：总张数 每种面额的使用数量（按面额从大到小排序）*/
void coinChange(int amount, vector<int>& denominations) {// 核心步骤1：将面额从大到小排序，确保优先使用大面额sort(denominations.begin(), denominations.end(), [](const int a, const int b) {return a > b;});int n = denominations.size();vector<int> count(n, 0);  // 记录每种面额的使用数量int totalCoins = 0;       // 总钱币数量// 核心步骤2：贪心选择——优先使用当前最大面额for (int i = 0; i < n; i++) {// 只有当剩余金额大于等于当前面额时才使用if (amount >= denominations[i]) {count[i] = amount / denominations[i];  // 计算最多能使用的张数totalCoins += count[i];                // 累加总张数amount -= count[i] * denominations[i]; // 减去已找零的金额}// 提前退出：金额已找完，无需继续循环if (amount == 0) {break;}}// 处理无法完全找零的情况if (amount > 0) {cout << "无法用给定面额完全找零，剩余金额：" << amount << endl;return;}// 输出结果cout << totalCoins << " ";for (int j = 0; j < n; j++) {if (j > 0) cout << " ";cout << count[j];}cout << endl;
}int main() {int typeCount;     // 面额种类数量int targetAmount;  // 目标找零金额cout << "请输入面额种类和目标金额（空格分隔）：";cin >> typeCount >> targetAmount;// 处理金额为0的特殊情况if (targetAmount == 0) {cout << "0";for (int i = 0; i < typeCount; i++) {cout << " 0";}cout << endl;return 0;}vector<int> denominations(typeCount);cout << "请输入" << typeCount << "种面额（空格分隔）：";for (int i = 0; i < typeCount; i++) {cin >> denominations[i];// 验证面额有效性if (denominations[i] <= 0) {cout << "错误：面额必须为正整数" << endl;return 1;}}coinChange(targetAmount, denominations);return 0;
}

核心逻辑解析

1. 排序面额

   sort(denominations.begin(), denominations.end(), greater<int>());
   

   这是贪心算法的关键，通过从大到小排序，确保每次都优先使用最大面额，从而最小化总张数。

2. 贪心选择过程

   if (amount >= denominations[i]) {count[i] = amount / denominations[i];totalCoins += count[i];amount -= count[i] * denominations[i];
   }
   

   对每种面额，计算最多能使用的张数（金额 / 面额），更新剩余金额和总张数。注意判断条件使用>=而非>，否则会漏掉 "金额恰好等于面额" 的情况。

3. 提前终止与异常处理

   • 当amount == 0时提前退出循环，减少无效计算
   • 若循环结束后仍有剩余金额，说明无法完全找零

测试案例与运行结果

案例 1：正常找零

输入：
4 41
25 1 10 5处理过程：
1. 排序后面额：25, 10, 5, 1
2. 25元：1张（41-25=16）
3. 10元：1张（16-10=6）
4. 5元：1张（6-5=1）
5. 1元：1张（1-1=0）输出：
4 1 1 1 1

案例 2：无法完全找零

输入：
210
3 5输出：
无法用给定面额完全找零，剩余金额：1

案例 3：金额为 0

输入：
3 0
1 2 5输出：
0 0 0 0

代码优化点说明

1. 命名规范：使用denominations（面额）、totalCoins（总张数）等语义化变量名，提高可读性。

2. 鲁棒性处理：

   • 验证输入面额为正数
   • 处理金额为 0 的边界情况
   • 检测无法找零的场景

3. 效率优化：

   • 排序后提前终止循环
   • 使用引用传递避免向量拷贝

贪心算法的局限性

虽然贪心算法实现简单、效率高（时间复杂度 O (n log n)，主要消耗在排序），但存在明显局限性：

• 仅适用于特定钱币系统（如面额为 {1,5,10,20,50}）
• 无法保证在任意面额组合下得到最优解

若需解决任意面额的最优找零问题，需采用动态规划算法，时间复杂度为 O (amount×n)，空间复杂度为 O (amount)。

总结

本文实现的贪心算法是解决常规钱币系统找零问题的高效方案，核心思想是 "每次选择最大面额"。代码通过排序、贪心选择和边界处理，完整实现了找零功能并输出详细结果。实际应用中，需根据具体钱币系统选择合适的算法 —— 常规货币系统用贪心，特殊面额组合则需动态规划。