找零问题贪心算法失效

### 贪心算法在找零问题上的失效原因

当处理特定的货币系统时，贪心算法可能会无法找到最优解。例如，在一个包含25美分、21美分、10美分、5美分和1美分的货币系统中，对于金额63美分而言，按照最大面值优先的原则分配硬币将会得到次优的结果[^4]。

具体来说，采用贪心策略会先尽可能多地使用高价值硬币，这可能导致最终使用的总硬币数量并非最小。在这个例子中，贪心算法会选择两个21美分硬币加上三个1美分硬币来组成63美分，总共用了五个硬币；然而实际上只需要三枚21美分硬币即可完成支付，这是更少的数量。

### 解决方案

为了克服这种局限性，可以考虑其他类型的算法：

#### 动态规划方法
这种方法能够确保总是获得全局最优解。它通过构建子问题表格的方式逐步解决问题，并记录下每一个阶段的最佳选择直到整个问题被解决为止。以下是基于Python实现的一个简单版本：

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

    return dp[-1] if dp[-1] != float('inf') else -1

此函数接受一组可用硬币`coins`和目标数额`amount`作为输入参数，返回构成该数额所需的最少硬币数目。如果没有办法恰好凑齐这个数额，则返回-1表示无解。

#### 回溯/递归搜索
另一种方式是利用回溯法尝试所有可能性并从中挑选出最佳路径。虽然效率较低但对于小型实例仍然适用。下面是一个简单的递归实现：

from functools import lru_cache

@lru_cache(maxsize=None)
def min_coins_recursive(coins, n):
    if n == 0:
        return 0
    res = float('inf')
    
    for c in coins:
        if n >= c:
            sub_res = min_coins_recursive(coins, n-c)+1
            res = min(res,sub_res)
            
    return res

这段代码同样接收相同形式的数据结构作为输入，并计算达到指定数值所需最少硬币数目的答案。这里采用了记忆化技术(`lru_cache`)以提高性能。