贪婪算法硬币找零最优解问题证明2

在贪心算法中，我们选择当前面值最大的硬币，直到找零金额为0为止。假设我们有一个最优解，使用最少的硬币数量来找零给定的金额。我们假设最优解为c1, c2, ..., cn，其中c1是最大的硬币面值。如果我们可以证明贪心算法的解也包含c1，那么我们就可以证明贪心算法的解是最优解。

假设最优解不包含c1，那么我们可以用更小的面值的硬币替换c1，得到一个解c2, c3, ..., cn，它使用的硬币数量比最优解少，这与最优解的假设矛盾。因此，最优解必须包含c1。

接下来，我们考虑用最大面值硬币c1取代一些其他硬币，看看是否可以得到更优的解。假设我们有一个最优解c1', c2', ..., cn'，其中c1' < c1。因为c1是最大的硬币面值，所以我们可以用若干个c1'来替换c1，得到一个新的解c1', c1', c2', ..., cn'，它使用的硬币数量比最优解少，这与最优解的假设矛盾。因此，我们得到的贪心算法的解也是最优解。

相关问题

头歌实验六 贪婪算法，找零钱

贪婪算法是一种基于贪心策略的算法，它在每一步都选择当前看起来最优的选项，以期望最终得到全局最优解。找零钱问题是一个经典的使用贪婪算法解决的问题。

假设你需要找零 $n$ 元钱，你手里有若干种面值的硬币，如 1 元、5 元、10 元、20 元、50 元、100 元等。现在要求尽可能少地使用硬币找零，该怎么办？

一个简单而有效的贪婪策略是每次选取面值最大的硬币进行找零。在找零过程中，每次都用尽可能多的面值最大的硬币，直到找完为止。这个方法的正确性可以通过反证法证明。

下面是一个 Python 实现：

def change(n, coins):
    """
    在硬币列表 coins 中找零 n 元钱，返回所需的硬币数量。
    """
    coins.sort(reverse=True)  # 按面值从大到小排序
    count = 0
    for coin in coins:
        while n >= coin:
            n -= coin
            count += 1
    return count

这个函数接受两个参数：要找零的金额 $n$ 和硬币列表 coins。它首先按硬币面值从大到小排序，然后从大到小遍历硬币列表，每次用尽可能多的当前面值的硬币进行找零，直到零钱全部找完为止。

例如，如果要找零 63 元，可用的硬币面值分别为 1 元、5 元、10 元、20 元和 50 元，可以这样调用该函数：

coins = [1, 5, 10, 20, 50]
n = 63
count = change(n, coins)
print(count)  # 输出 5

这个例子中，找零 63 元需要 5 个硬币，分别是 50 元、10 元、1 元、1 元、1 元。