贪心算法python程序代码

当然，下面是一个简单的Python示例，演示如何使用贪心算法解决一个问题：给定一组硬币面额（如常见的1元、5元、10元等），找到支付一个整数金额的最少硬币数量。这里我们采用典型的贪心策略——总是优先使用最大面额的硬币。

def coin_change(coins, amount):
    # 初始化一个列表，用于存储每个金额所需的最少硬币数
    min_coins = [float('inf')] * (amount + 1)

    # 首先，不需要任何硬币时，最小硬币数为0
    min_coins[0] = 0

    for coin in coins:
        # 遍历所有的硬币面额
        for i in range(coin, amount + 1):  # 只考虑大于等于硬币面额的金额
            # 如果加上这个硬币比单独处理那个金额少，更新计数
            if i - coin < min_coins[i]:
                min_coins[i] = i - coin

    return min_coins[amount] if min_coins[amount] != float('inf') else -1  # 返回最小硬币数，若无法构成，则返回-1

# 示例
coins = [1, 5, 10]
amount = 13
print(coin_change(coins, amount))  # 输出：2，因为用两个5元硬币就可以支付13元