我想知道每个面额都有无限数量硬币的硬币找零问题的算法思想。表示如何应用 DP(就像标准硬币找零问题) 例如在集合 1,10,15 中, 零钱 35 gives--2 个 10 硬币和 1 个 15 硬币
同时给我一个暴力破解算法的想法。我知道遍历所有集合。但是如何在暴力破解时改变每个硬币的数量
最佳答案
我会考虑逐步构建解决方案,归纳地:
可用的硬币有 1c、5c、10c、25c(您可以根据需要调整它们)
- 1c = 1 X 1c 的最小硬币。最多 4 美分,我们需要 1c 硬币,因为这是最小的面额。
- 对于 5 美分,我们有一个 5c 硬币。结合上面的 4c,我们可以生成 1 到 9 之间的任何数字。
- 对于 10 美分,我们需要 1 X 10c。结合以上三者,我们可以生成 1 到 19 之间的任意数字。
- 对于 20c,我们需要 2 x 10c,因为 20 可以被 10 整除。
如果您可以归纳地提出问题,解决它可能会更容易。
编辑:
好了,下面再尝试解释一下动态规划的解法:
考虑一个包含 x
行(x
是不同面额的数量)和 n
列(n
是您必须使用最少面额建立的金额)。此表中的每个单元格代表一个不同的子问题,最终将包含它的解决方案。假设:
第 1 行代表集合 {1c}
即在第 1 行中您可以使用无限 1c
第 2 行表示集合 {1c, 10c}
即在第 2 行中您可以无限 1c
和 10c
第 3 行表示集合 {1c, 10c, 15c}
等等...
每列代表您要构建的数量。
因此,每个单元格对应一个小的子问题。例如(为简单起见索引从1开始),
cell(1, 5)
==> 仅使用 {1c}
构造 5c
cell(2, 9)
==> 使用 {1c, 10c}
构造 9c
cell(3, 27)
==> 使用 {1c, 10c, 15c}
构造 27c
现在你的目标是得到 cell(x, n)
解决方案:
从最简单的问题开始解决表格。求解第一行很简单,因为在第一行中唯一可用的面额是 {1c}
。第 1 行中的每个单元格都有一个平凡的解决方案,导致 cell(1, n)
= {nx1c}
(n
个 硬币1c
).
现在继续下一行。概括第二行,让我们看看如何解决(比如)cell(2, 28)
,即使用 {1c, 10c}
构造 28c
>。在这里,您需要做出决定,是否在解决方案中包含 10c
以及多少硬币。你有 3 个选择 (3 = 28/10 + 1)
选择 1
:
取 {1x10c}
和上一行的其余部分(存储在 cell(1, 18)
中)。这给你 {1x10c, 18x1c}
= 19 个硬币
选择 2
:
取 {2x10c}
和上一行的其余部分(存储在 cell(1, 8)
中)。这给你 {2x10c, 8x1c}
= 10 个硬币
选择 3
:
不取 10c
和上一行的其余部分(存储在 cell(1, 28)
中)。这给你 {28x1c}
= 28 个硬币
显然,选择 2 是最好的,因为它需要更少的硬币。将其写在表中,然后继续。该表将一次填充一行,并在一行内按数量递增的顺序填充。
按照上述规则,您将到达 cell(x, n)
,解决方案将是在 n/p + 1
备选方案之间进行选择,其中 p
= x
行中的最新面额。最好的选择就是您的答案。
该表实际上记住了较小问题的解决方案,因此您无需一次又一次地解决它们。
关于algorithm - 每种面额无限数量的硬币找零问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1518330/