什么是贪心算法

贪心算法是一种在每一步选择中都选择当前最优的选择，而不是总最优的选择。贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心本质

原问题的整体最优解可以通过一系列局部最优解的选择得到。应用同一规则，将原问题分解为若干子问题，子问题的最优解可以由子问题的子问题得到，最终得到原问题的最优解。

求解步骤

贪心策略->局部最优解->全局最优解

问题描述

问题描述
假设我们有以下面值的硬币：1 分、5 分、10 分、25 分。我们需要找零 n 分钱，如何用最少的硬币数量来凑齐这个金额。

Python代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def make_change(cents):
    """
    使用贪心算法实现找零的金额
    返回值：
    list:包含最少硬币的列表
    """
# 硬币面值
    coins = [25, 10, 5, 1]
    # 存储结果的列表
    result = []
    
    # 遍历每种面值的硬币
    for coin in coins:
        # 只要当前金额大于等于硬币面值，就使用该硬币
        while cents >= coin:
            result.append(coin)
            cents -= coin
    
    return result

# 测试
if __name__ == "__main__":
    amount = 63  # 需要找零的金额
    change = make_change(amount)
    print(f"找零 {amount} 分钱，需要的硬币是: {change}")
    print(f"总共需要 {len(change)} 个硬币")