最少硬币问题

最少硬币问题是一个经典的贪心算法问题。给定一定数量的面额不同的硬币和一个总金额，找出能够凑出总金额的最少硬币数。

贪心算法的思路是，每次选择当前面值下最大的硬币，直到凑够总金额。这个算法的正确性证明需要用到贪心策略的贪心选择性质和最优子结构性质。

下面是最少硬币问题的 Python 实现：

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count

其中，`coins` 是硬币面值的列表，`amount` 是总金额。算法首先按照面值从大到小排序，然后不断选择最大的硬币，直到凑够总金额。最后返回所需硬币的最小数量。