最少硬币组合问题2:贪心算法【附算法导论习题答案下载】

  |  

摘要: 最少硬币组合问题的一种可以贪心的面额集

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在上一篇文章 最少硬币组合问题1:完全背包 中,我们介绍了最少硬币组合问题对任意面额集的通用解法,也就是动态规划,时间复杂度为 $O(nk)$,其中 n 为要凑出的金额,k 为面额集中的面额种数。

一个比较直接的贪心策略是,每次都选不大于剩余金额的最大面值,如果这个策略可以得到最优解,就可以形成贪心算法,$O(k)$ 解决问题。这个贪心算法通常并不成立,那么问题就在于面额集满足什么条件的时候,该贪心策略可以得到最优解。

《算法导论》第三版的习题 16-1 给出了一种可以贪心的面额集,也就是呈等比数列的面额集。本文我们来解决这道题,首先证明最少硬币组合问题满足最优子结构,然后对等比数列面额集证明贪心选择性质。这个证明过程比较有意思,是通过证明所有的非贪心解都是非最优的来完成证明的,值得一看。

《算法导论》的习题质量非常高,理论和实践均有涉及,很多都有论文的背景,推荐各位可以刷一刷,这里分享算法导论第三版的习题答案,从第一章到附录的习题答案全有,一共 500 多页,可以通过以下链接下载。

问题描述

下面是《算法导论》第 3 版的思考题 16-1。

题解

最优子结构

首先证明最少硬币找零问题具有最优子结构,贪心和动态规划都需要这个性质。证明最优子结构有通用的套路,《算法导论》管它叫 cut-and-paste 方法。

假设最少硬币凑 n 元的最优解使用了 $x$ 枚硬币,最优子结构的含义是若最优解中使用了面值为 $s$ 的硬币,那么该最优解中一定包含了最少硬币凑 $n-s$ 元的最优解,即 $x-1$。

下面是 cut-and-paste 论证:对最少硬币凑 $n-s$ 元的问题,如果存在少于 $x - 1$ 枚硬币凑出 $n-s$ 元的解,则可以用该解构造少于 $x$ 枚硬币凑出 $n$ 元的解,与 $x$ 为凑出 $n$ 元的最优解矛盾。

因此最少硬币找零问题具有最优子结构。

(a) 贪心算法成立的一例

对于 25, 10, 5, 1 这一组面额,贪心算法如下:

  • step1:给 $q = \lfloor\frac{n}{25}\rfloor$ 枚 25 面值硬币,剩余金额 $n_{q} = n \mod 25$;
  • step2:给 $d = \lfloor\frac{n_{q}}{10}\rfloor$ 枚 10 面值硬币,剩余金额 $n_{d} = n_{q} \mod 10$;
  • step3:给 $k = \lfloor\frac{n_{d}}{5}\rfloor$ 枚 5 面值硬币,剩余金额 $n_{k} = n_{d} \mod 5$;
  • step4:给 $p = n_{k}$ 枚 1 面值硬币,剩余金额 0。

下面证明对于面额集 $\{25, 10, 5, 1\}$ 这个贪心算法的正确性。

贪心算法的等价描述如下,若 $n=0$ 则最优解为不给硬币。若 $n>0$ 则看不大于 $n$ 的最大面值 $c$,给一枚 $c$,然后递归地解凑 $n-c$ 元的问题。贪心选择性质要证明的事最优解中至少要包含一枚 $c$。

考虑 $n$ 的各种情况:

$1 \leq n < 5$:$c = 1$,此时有 $c$ 可选,最优解自然含 $c$;

$5 \leq n < 10$:$c = 5$,若最优解不含 5 元面额,则只能含 1 元面额。但是将 $5$ 个 1 元面额换成 $1$ 个 5 元面额,即可将硬币减少 4 枚。因此最优解一定含 $c$;

$10 \leq n < 25$:$c = 10$,若最优解不含 10 元面额,则只能含 1 元、5 元面额。但是无论怎样组合,总能找到一个和为 10 的子集,将该子集替换为 1 枚 10 元面额即可减少硬币枚数。因此最优解一定含 $c$;

$25 \leq n$:$c = 25$,若最优解不含 25 元面额,则只能含 1 元、5 元、10 元面额。若有 $3$ 个 10 元面额,则可以换为 5 元面额和 25 元面额,减少了 1 枚;若有至多 2 个 10 元面额,则可以找到和为 $25$ 的子集,将该子集替换为 1 枚 25 元面额即可。因此最优解一定含 $c$。

(b) 等比面额集的贪心算法

贪心算法与 (a) 中一样,首先找到 $j = \max\{0\leq i \leq k: c^{i} \leq n\}$,给一枚 $c^{j}$,递归地解 $n - c^{j}$ 的问题,持续进行下去,直至要凑的金额耗尽。最终得到的解是使用 $\lfloor\frac{n}{c^{k}}\rfloor$ 枚 $c^{k}$ 面额硬币、$\lfloor\frac{n\mod c^{i+1}}{c^{i}}\rfloor$ 枚 $c^{i}$,$i=0,1,\cdots,k-1$。

为了证明以上策略可以得到最优解,首先证明以下引理。

引理

对于 $i=0,1,\cdots,k$,记 $a_{i}$ 为最优解中用 $c^{i}$ 面额硬币的数量,则对 $i=0,1,\cdots,k-1$,有 $a_{i} < c$。

证明(反证)

若存在某 $a_{i} \geq c$,$i=0,1,\cdots,k-1$,则可以用 1 枚 $c^{i+1}$ 面额硬币代替 $c$ 枚 $c^{i}$ 面额硬币。则 $a_{i}$ 可减少为 $a_{i} - c + 1$,由于 $c < 1$ 所以硬币数减少了,与假设矛盾。

$\Box$

下面证明所有非贪心的解都是非最优的。

定理

令 $j = \max\{0\leq i \leq k: c^{i} \leq n\}$,按照贪心策略,非贪心的解中是不包含 $c^{j}$ 或更高面额硬币的,则该解一定不是最优解。

证明(反证)

记 $a_{i}$ 为非贪心解中使用 $c^{i}$ 的数量,$i=0,1,\cdots,j-1$,且 $\sum\limits_{i=0}\limits^{j-1}a_{i}c^{i} = n$。

因为 $n \geq c^{j}$,所以 $\sum\limits_{i=0}\limits^{j-1}a_{i}c^{i} \geq c^{j}$。

假设非贪心解是最优的,则由引理有 $a_{i} \leq c - 1$,$i=0,1,\cdots,j-1$,于是:

与 $\sum\limits_{i=0}\limits^{j-1}a_{i}c^{i} \geq c^{j}$ 矛盾,因此非贪心解一定非最优。

$\Box$

由于等比面额集上所有非贪心解都是非最优的,贪心算法自然成立。根据算法描述,时间复杂度为 $O(k)$。

(c) 贪心策略不成立的一例

例如 $\{1, 10, 25\}$ 这个面额集,要凑出 $n=30$ 元。贪心算法给出 1 枚 25 面额硬币和 5 枚 1 元面额硬币,共 6 枚硬币。然而非贪心的策略可以给出 3 枚 10 面额硬币的结果,仅需 3 枚。

(d) 所有面额集都成立的 DP 算法

由于问题具有最优子结构,可以考虑 DP 算法。

记面额集为 $\{d_{1}, d_{2},\cdots,d_{k}\}$,由于其中包含 1 面额的硬币,因此可以凑出所有金额 $j \geq 1$。

记 $dp[j]$ 为凑出 $j$ 元所需的最少硬币数,由最优子结构,若最优接种使用了面额 $d_{i}$,则:

对于 $j \leq 0$,$dp[j] = 0$ 为边界情况。

遍历面额集中的所有面额,可以得到以下状态转移方程:

最终的答案为 $dp[n]$,推导每个 $dp[j]$ 的时候,都需要遍历面额集的 $k$ 个面额,因此总时间复杂度为 $O(nk)$。

在文章 最少硬币组合问题1:完全背包 中讨论的就是用该 DP 算法解决一般面额集的最少硬币组合问题。

总结

等比数列只是其中一种可贪心的面额集,能不能找到更多的可贪心面额集,或者更激进一点,有没有贪心算法成立的充分必要条件。

退而求其次,有没有比较通用的算法,任意给定一个面额集后可以通过该算法来判断该面额集能不能贪心。

事实上这两个问题非常复杂,在学术论文中可以找到一些结果,以后有机会在跟大家分享。


Share