硬币兑换证明贪心算法是否是最优解

硬币兑换问题是一个经典的贪心算法问题。贪心算法的思想是每次选择当前最优解，以期望最终得到全局最优解。对于硬币兑换问题，我们可以采用以下贪心策略：

1. 优先选择面值最大的硬币，直到无法再选为止。
2. 如果当前面值无法选，则选择下一个面值最大的硬币。

证明这个贪心策略的正确性，我们需要证明贪心策略产生的解一定是最优解。我们可以采用反证法来证明。

假设存在一个最优解，它的硬币组合不同于贪心策略产生的硬币组合。我们可以将这个最优解分为两部分：第一部分是与贪心策略相同的硬币组合，第二部分是不同于贪心策略的硬币组合。

我们可以发现，第一部分的硬币组合一定是最优解，因为它与贪心策略相同，而贪心策略是每次选择当前最优解。因此，第一部分的硬币组合一定是最优解。

对于第二部分的硬币组合，我们可以发现，它的总面值一定小于等于贪心策略产生的硬币组合的总面值。因为贪心策略是每次选择当前最优解，而第二部分的硬币组合不同于贪心策略，因此它的总面值一定小于等于贪心策略产生的硬币组合的总面值。

因此，我们可以得出结论：贪心策略产生的硬币组合一定是最优解。

以下是一个Python实现的例子：

def coin_change(coins, amount):
    coins.sort(reverse=True) # 按面值从大到小排序
    res = 0
    for coin in coins:
        if amount >= coin:
            res += amount // coin
            amount %= coin
    return res if amount == 0 else -1 # 如果无法兑换，则返回-1

coins = [25, 10, 5, 1]
amount = 41
print(coin_change(coins, amount)) # 输出：5