贪心算法实现最少硬币找钱问题

最少硬币找钱问题是一个经典的问题，贪心算法可以用来解决这个问题。

具体实现步骤如下：

1. 准备一个硬币面值数组（假设为coins）和一个需要找零的金额（假设为amount）。

2. 定义一个变量total表示已经找到的硬币总数，初始值为0。

3. 对硬币面值数组进行排序，从大到小排列。

4. 遍历硬币面值数组，对每个硬币面值执行以下操作：

a. 如果硬币面值小于等于需要找零的金额，就将该硬币面值加入结果集中，并将需要找零的金额减去该硬币面值。

b. 如果硬币面值大于需要找零的金额，就跳过该硬币面值。

c. 如果需要找零的金额已经减到0，就退出循环。

5. 如果需要找零的金额减到0了，就返回结果集的长度（即所需硬币的最小数量），否则返回-1，表示无法找零。

代码实现如下：

def coinChange(coins, amount):
    coins.sort(reverse=True)   # 从大到小排序
    total = 0
    res = []   # 结果集
    for coin in coins:
        while amount >= coin:
            res.append(coin)
            amount -= coin
            total += 1
        if amount == 0:
            return total
    return -1   # 无法找零

测试代码：

coins = [1, 5, 10, 25]
amount = 41
print(coinChange(coins, amount))   # 输出3，即需要3枚硬币才能找到41美分