找零问题适用贪心算法的证明

对于找零问题，贪心算法可以得到最优解。证明如下：

假设有一个找零问题，需要找给顾客 n 元钱，现有面值为 d1, d2, ..., dm 的硬币。我们需要找到最少的硬币数来凑出 n 元钱。

我们可以使用贪心算法来解决这个问题。具体来说，我们可以按照硬币面值从大到小的顺序来考虑。每次我们选择面值最大的硬币，直到无法再选择硬币为止。然后我们再选择面值次大的硬币，直到无法再选择硬币为止。以此类推，直到凑出 n 元钱为止。

假设我们使用贪心算法得到的解为 S = {c1, c2, ..., ck}，其中 ci 表示第 i 枚硬币的面值。我们需要证明，这个解是最优解。

假设存在一个最优解 T = {d1, d2, ..., dn}，其中 di 表示第 i 枚硬币的面值，并且 T 中硬币的总数小于 S 中硬币的总数。我们需要证明，这个假设是不成立的。

我们可以将 T 和 S 中的硬币按照面值从大到小的顺序排列。假设在某个位置 i 上，T 和 S 中的硬币不同。也就是说，Ti != Si。

由于 Ti 的面值比 Si 的面值小，所以 Ti 无法凑出 Si。因此，我们需要使用 Si 来凑出 Ti。但是，由于 T 中的硬币总数小于 S 中的硬币总数，所以在 S 中一定存在一个硬币 Sj，使得 Sj 的面值小于等于 Ti 的面值，并且 Sj 没有被 T 中的任何一个硬币凑出过。

因此，我们可以将 T 中的 di 替换为 Sj，得到一个新的解 T'。由于 Sj 的面值小于等于 Ti 的面值，并且 Sj 没有被 T 中的任何一个硬币凑出过，所以 T' 中的硬币总数小于 T 中的硬币总数。这与 T 是最优解的假设矛盾。

因此，假设不成立，S 是最优解。