许多人认为身上如果带太多的零钱会让行动变得不方便,因此会希望商店店员在找零钱的时候能够以最少的硬币数来找,而不是全部都用 1 元塞给我们。

这篇文章将会直接以动态规划来解决问题,如果您还不熟悉动态规划的话可以先查看这篇文章:

假设现在店家有 1、5、10、25 元面额的硬币,不限数量,当店员要找给客人 31 元的时候,可以怎么找?例如:

  1. 给 31 个 1 元。(那店员怕是要被揍了)
  2. 给 1 个 25 元、1 个 5 元、1 个 1 元。
  3. 给 3 个 10 元、1 个 1 元。

店员如果是拿 1 个 25 元、1 个 5 元、1 个 1 元,只需要 3 枚硬币就可以凑成 31 元,而客人拿了也会很开心。

您可能会觉得,这问题不是很简单吗?只要从最大面额开始找就好了。确实没错,但如果多了一种 21 元的硬币面额会怎么样呢?

重新叙述问题:假设现在店家有 1、5、10、21、25 元面额的硬币,不限数量,当店员要找给客人 63 元的时候,最少要多少个硬币?

如果我们从最大面额开始找,需要 2 个 25 元,1 个 10 元,3 个 1 元,共 6 枚硬币,但这个找法却不是这个问题的最佳解……因为我们其实可以只用 3 个 21 元的硬币来组成 63 元。当然,也是因为这个题目已经设计好的关系(63 明显就是 21 乘 3),才能让我们快速地找出最佳解,如果换成其它数字,可能就不是那么容易了。

以 Top-down 的方式来思考上面的问题。因为在最后一步要能够以最少硬币数凑出 63 元,而在运行最后一步前,有可能已经凑出了 62 元、58 元、53 元、42 元或是 38 元,所以要从 0 元凑到 63 元,最少的硬币数就是凑到 62 元的最少硬币数、凑到 58 元的最少硬币数、凑到 53 元的最少硬币数、凑到 42 元的最少硬币数和凑到 38 元的最少硬币数中的最小值再加 1……依此类推。最小的问题为凑 0 元(最少需要 0 个硬币)、凑 1 元(最少需要 1 个硬币)和凑 2 ~ 24 元,但是凑 2 ~ 24 元我们不太能够直接知道最少要几个硬币,所以不要把它当作是基本案例(base case)。

以程序来解题的话,我们可以写出以下的递归函数:

当然,这个函数的性能很差,先不管它。因为还有个更严重的地方,那就是这个程序目前只能固定地用 1、5、10、21、25 元面额的硬币来计算,功能实在太弱了!所以我们要把程序改成可以从函数参数输入硬币的面额(假设至少有一种面额,每种面额至少会有 1 元,且会递增输入)。而因为输入的最小面额可能会大于 1 元,所以需要注意到无解的情形(例如面额只有 3 元和 7 元,就不可能凑到 11 元)。若是无解,则把结果设为「最大整数」。

程序强化功能后如下:

由于以上代码有重叠子问题,所以可以用动态规划的记忆法来优化或是用制表法将其改写成迭代函数。

以制表法为例,改写如下:

dp 数组的索引 i 所保存的值就是凑到 i 元时最少需要的硬币数量。

接着我们就要来利用上面这支程序去取得最少硬币数量的组合方式了。

为了让各位充分理解上面这支程序的用途,就先把程序改为直接在屏幕上输出结果,而不是透过函数回传出来。代码如下:

想要知道硬币的组合方式,可以再添加一个长度为 amount + 1 的数组,这个数组里面的元素都是长度为硬币面额数量的数组,且数值初始化为 0,用来保存凑到 i 元时,各种面额的硬币的数量。代码如下:

如果您觉得以上代码会吃掉太多内存空间,而且计算过程中还要在那边拷贝数组,看起来不是很好的话,其实也可以考虑只用长度为 amount + 1 的一维数组,去记录每个阶段的问题在最佳解时最后拿到的硬币面额(的索引值)。最后再反推回去就可以知道到底拿了哪些面额的硬币了。