硬币找零问题

收银员找零时会先拿不超过金额的最大硬币,再拿下一枚,对欧元或美元来说,这样总能得到最少的硬币。但如果把硬币换成 1、3 和 4,同样的习惯会用三枚硬币付 6,而两枚就够了。动态规划能为任何硬币组合找到真正的最小值。

一排金额及凑出各金额的最少硬币,下方是三种不同大小的硬币
一排金额及凑出各金额的最少硬币,下方是三种不同大小的硬币

两个问题

硬币找零问题有两种形式。第一种求刚好凑出某个金额所需的最少硬币数,也称为找零问题。第二种问有多少种不同的硬币组合能凑出它。两种形式中每种硬币都可以使用任意多次,而且都是由较小金额的答案构建出每个金额的答案来求解的。

一步步求最少硬币

为从 0 到目标的每个金额建一个格子,排成一行。金额 0 需要 0 枚硬币;其他金额一开始都是无穷大。按顺序遍历金额,对每个金额尝试每枚不超过它的硬币 c:金额减 c 的格子再加一枚硬币就是一个候选。保留最小的。每个格子只依赖它左边已经确定的格子,所以一遍就能填满这一行。

一个例子

硬币为 1、3 和 4 时:金额 1 需要 1 枚硬币,2 需要 2 枚,3 需要 1 枚(一枚 3),4 需要 1 枚。对 5,尝试 1(4 需要 1 枚,共 2 枚)、3(2 需要 2 枚,共 3 枚)和 4(1 需要 1 枚,共 2 枚):最好是 2 枚。对 6,尝试 1(5 需要 2 枚,共 3 枚)、3(3 需要 1 枚,共 2 枚)和 4(2 需要 2 枚,共 3 枚):最好是 2 枚,即 3 + 3。贪心则会付 4 + 1 + 1。

计算方法数

要计算组合数,就逐个加入硬币。只有第一种硬币时,每个金额要么有一种凑法,要么凑不出来。加入一种新硬币 c 时,凑出金额 a 的方法数等于原来不用 c 的方法数,加上在仍可使用 c 的情况下凑出 a − c 的方法数,因为其中每一种再加一枚 c 都成为凑出 a 的一种方法。硬币为 1、2 和 5 时,凑出 5 有 4 种方法:5、2 + 2 + 1、2 + 1 + 1 + 1 和 1 + 1 + 1 + 1 + 1。

什么时候贪心就够了

如果贪心总能给出最少硬币数,这样的硬币体系称为规范硬币系统。大多数现代货币都是这样设计的。1994 年,David Pearson 提出了一种检验方法,检查一个硬币体系所需的步数只随硬币种数呈多项式增长。英国旧硬币就不是规范的:贪心会把 48 便士付成一枚半克朗、一枚先令和一枚六便士,而两枚弗罗林就够了。

动手探索

打开应用,切换到“表格”视图,按“单步”。在“最少硬币”模式中,橙色格子是正在计算的金额,蓝色格子是这枚硬币留下的较小金额;下面一行记录最后一枚硬币,最后沿着这一行倒推读出硬币。切换到“方法数”,观察随着每种硬币的加入,计数一行一行地增长。

常见问题

硬币找零问题是背包问题吗?

是近亲。最少硬币版本是一个完全背包问题:每种硬币是一件物品,重量为其面值,背包必须恰好装满,目标是物品数最少。

时间复杂度是多少?

对 k 种硬币和金额 A,两个版本都是 O(k·A)。最少硬币的表有 A + 1 个格子,方法数的表有 (k + 1)·(A + 1) 个格子,不过如果原地更新格子,一行就够了。

为什么要按固定顺序计算硬币?

如果每个金额都尝试每种硬币,1 + 2 和 2 + 1 就会被算作两种方法。逐行加入硬币意味着一个组合总是先由较早的硬币构成,所以每个组合恰好只算一次。

能为方法数倒推读出硬币吗?

不能作为单一答案读出,因为组合有很多种。最少硬币版本记录每个金额的最后一枚硬币,这足以重建一种最优组合。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

试试硬币找零