python钱币转换代码

### Python 实现货币兑换或硬币找零的代码示例

为了实现给定面额下的最小硬币数计算，可以采用贪心算法来解决问题。这种方法适用于某些特定情况，在这些情况下总是优先选用最大可能的硬币面值[^1]。

def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)  # 将硬币按降序排列
    count = 0
    
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
            
    if amount != 0:
        return "无法完成找零"
    
    return count

上述方法虽然直观易懂，但在一些特殊场景下可能会失效。因此更通用的方法是动态规划法：

def coin_change_dp(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0 and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[-1] if dp[-1] != float('inf') else '无法完成找零'

这两种方式都可以用于解决自动售货机中的找零问题，确保顾客能够获得正确的找零金额并尽可能减少使用的硬币数量[^2]。

对于输入参数`coins`和`amount`有如下约束条件：列表长度介于1到12之间；每个元素大于等于1小于等于某个上限值；而总金额则非负整数值[^3]。