Python 中贪心算法的基本思想和特点

Python 中贪心算法的基本思想是，在每个决策点上都采取当前状态下最优的决策，从而希望最终能够得到全局最优解。具体来说，贪心算法不会考虑全局的问题，而仅仅考虑当前的情况，也就是只选择最优的策略。

贪心算法的特点是具有高效性和局部最优性。由于大多情况下贪心算法是按照某种规则从小到大或从大到小依次处理的，因此该算法因其高效性而受到广泛的应用。但是由于局部最优性的限制，贪心算法并不能保证一定能够得到全局最优解。

下面以贪心算法的应用场景-零钱兑换为例进行代码演示，假设有以下三种面额的钱币：1元、2元、5元。现在需要用最少的钱币数量来凑齐11元钱。

def change_money(n, coins):
    """
    :param n: 需要兑换的钱数
    :param coins: 面额列表
    :return: 最少的硬币数量
    """
    # 对coins进行降序排序，方便后续处理
    coins.sort(reverse=True)
    cnt = 0
    for coin in coins:
        if n == 0:  # 兑换完毕，结束循环
            break
        cnt += n // coin  # 兑换硬币的数量
        n = n % coin  # 剩余需要兑换的钱数
    return cnt

# 测试
print(change_money(11, [5, 2, 1]))  # 输出3

代码解释：

这段代码首先对给定的面额列表 coins 进行降序排序，方便后续处理。然后，在循环中不断选择当前面值最大的硬币，直到剩下的钱数为0为止。具体的实现过程是，用当前硬币的面值去除需要兑换的钱数n，得到能兑换的硬币数量，并将这个数量累加到变量cnt中。接着，用需要兑换的钱数n除以硬币的面值，得到剩余需要兑换的钱数。

在本例中，最优的策略是选择硬币面值最大的硬币来尽可能地凑齐钱数，直到钱数兑换完毕。