最小硬币找零问题

题目

最小硬币找零问题

信息

• 类型：问答
• 难度：⭐

考点

贪心策略设计,问题分析能力,基础循环实现

快速回答

使用贪心算法解决最小硬币找零问题的核心步骤：

1. 从最大面额硬币开始遍历
2. 对每个面额，尽可能多地使用：
   • 计算当前面额最多可用数量 = 剩余金额 / 面额值
   • 更新剩余金额 = 剩余金额 % 面额值
   • 累加硬币数量
3. 当剩余金额为0时结束

时间复杂度：O(n)，其中n是硬币种类数。

解析

问题描述

给定一个金额N和一组硬币面额coins（如[1, 5, 10]），每种硬币数量无限。求组成金额N所需的最少硬币数量。假设coins已按升序排列，且包含面额1（保证有解）。

贪心算法原理

贪心策略的核心是：每一步都选择当前最优解。对于硬币找零问题：

• 最优子结构：大问题的最优解包含子问题的最优解
• 贪心选择性质：每次选择不超过剩余金额的最大面额硬币
• 可行性：因包含面额1的硬币，总能找零成功

代码实现（Python）

def min_coins(amount, coins):
    coins.sort(reverse=True)  # 确保从大到小
    count = 0
    for coin in coins:
        if amount == 0:
            break
        # 计算当前硬币最多可用数量
        num_coins = amount // coin
        count += num_coins
        amount -= num_coins * coin
    return count

# 示例
print(min_coins(28, [1, 5, 10]))  # 输出：4 (10*2 + 5*1 + 1*3)

执行过程示例（amount=28）

1. 取coin=10：28//10=2枚，剩余8元
2. 取coin=5：8//5=1枚，剩余3元
3. 取coin=1：3//1=3枚，剩余0元
4. 总硬币数=2+1+3=6

最佳实践

• 排序预处理：先按面额降序排列
• 提前终止：当剩余金额为0时立即结束循环
• 边界处理：检查输入金额是否非负

常见错误

• 未排序处理：直接使用输入硬币数组，导致从小面额开始
• 忽略整数除法：应用浮点数除法导致计数错误
• 无效面额假设：误认为贪心法适用于所有面额组合（如[1,3,4]找零6时贪心失效）

扩展知识

• 贪心法局限性：当面额不满足贪心选择性质时（如[1,3,4]），需用动态规划求解
• 实际应用场景：自动售货机找零、支付系统零钱分配
• 复杂度对比：贪心法O(n) vs 动态规划O(n*amount)