python贪心算法

作者：恋你如初发布日期:2026-01-22 浏览:119

# 贪心算法示例：找零问题

def find_min_coins(coins, amount):
    # 对硬币面值从大到小排序
    coins.sort(reverse=True)

    # 记录使用的硬币数量
    num_coins = 0

    # 遍历每种硬币，尽量多使用当前面值的硬币
    for coin in coins:
        if amount >= coin:
            num_coins += amount // coin
            amount %= coin

        # 如果已经凑够了金额，返回结果
        if amount == 0:
            return num_coins

    # 如果无法凑够金额，返回 -1 表示无解
    return -1 if amount != 0 else num_coins

# 示例调用
coins = [1, 2, 5]
amount = 11
print(find_min_coins(coins, amount))  # 输出: 3 (5 + 5 + 1)

# 解释：
# 1. 我们首先对硬币面值进行降序排序。
# 2. 然后遍历每种硬币，尽量多使用当前面值的硬币。
# 3. 每次使用硬币后，更新剩余需要凑齐的金额。
# 4. 如果在某一步能够恰好凑够金额，则返回已使用的硬币数量。
# 5. 如果遍历完所有硬币仍然无法凑够金额，则返回 -1 表示无解。

上一篇：反向输出字符串python

下一篇：python sys.path.append