一分耕耘，一分收获！既然打开了这篇文章《Python算法如何解决找零问题？》，就坚持看下去吧！文中内容包含等等知识点...希望你能在阅读本文后，能真真实实学到知识或者帮你解决心中的疑惑，也欢迎大佬或者新人朋友们多留言评论，多给建议！谢谢！

找零问题的最优解可通过贪心算法（特定体系）或动态规划（通用）实现，前者在人民币等体系下有效，后者适用于所有情况。

找零问题是经典的优化问题，目标是用最少数量的硬币凑出指定金额。假设你有一组固定面额的硬币，比如 1元、5元、10元、25元，现在需要支付一定金额，求最少需要多少枚硬币。

贪心算法（适用于特定硬币体系）

在某些国家的货币体系中（如人民币、美元），使用贪心策略可以得到最优解：每次都选不超过剩余金额的最大面值硬币。

def make_change_greedy(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序
    count = 0
    for coin in coins:
        if amount == 0:
            break
        count += amount // coin
        amount %= coin
    return count if amount == 0 else -1  # 如果无法凑出，返回-1
<h1>示例</h1><p>coins = [1, 5, 10, 25]
amount = 67
print(make_change_greedy(coins, amount))  # 输出: 6 (25<em>2 + 10</em>1 + 5<em>1 + 1</em>2)
</p>

注意：这种方法只在硬币面额满足“规范性”时有效，例如不能处理 [1, 3, 4] 面额下对 6元 的最优解（贪心会选4+1+1=3枚，但最优是3+3=2枚）。

动态规划（通用解法）

对于任意硬币组合，动态规划能保证找到最小硬币数。

思路是构建一个数组 dp[i] 表示凑出金额 i 所需的最少硬币数，初始设为无穷大，dp[0] = 0。

def make_change_dp(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin 示例<p>coins = [1, 3, 4]
amount = 6
print(make_change_dp(coins, amount))  # 输出: 2 (3+3)
</p>

这个方法时间复杂度为 O(amount × len(coins))，空间复杂度 O(amount)，适合大多数实际场景。

输出具体找零方案

如果还需要知道用了哪些硬币，可以在DP过程中记录路径。

def make_change_with_path(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    parent = [-1] * (amount + 1)  # 记录转移来源
<pre class="brush:php;toolbar:false"><code>for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i and dp[i - coin] + 1 < dp[i]:
            dp[i] = dp[i - coin] + 1
            parent[i] = coin

if dp[amount] == float('inf'):
    return -1, []

# 回溯找出使用的硬币
change_coins = []
current = amount
while current > 0:
    coin = parent[current]
    change_coins.append(coin)
    current -= coin

return dp[amount], change_coins</code>

示例

coins = [1, 3, 4] amount = 6 num_coins, used = make_change_with_path(coins, amount) print(f"最少硬币数: {num_coins}, 使用的硬币: {used}") # 最少硬币数: 2, 使用的硬币: [3, 3]

这样不仅能知道最少数量，还能还原出具体的找零组合。

基本上就这些。根据硬币体系选择合适方法——标准货币可用贪心，一般情况推荐动态规划。不复杂但容易忽略边界和不可达情况。

本篇关于《Python如何高效解决找零问题？》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！