algorithm - 每种面额无限数量的硬币找零问题

Question

我想知道每个面额都有无限数量硬币的硬币找零问题的算法思想。表示如何应用 DP(就像标准硬币找零问题)例如在集合 1,10,15 中，零钱 35 gives--2 个 10 硬币和 1 个 15 硬币

同时给我一个暴力破解算法的想法。我知道遍历所有集合。但是如何在暴力破解时改变每个硬币的数量

Answer 1

我会考虑逐步构建解决方案，归纳地:

可用的硬币有 1c、5c、10c、25c(您可以根据需要调整它们)

1. 1c = 1 X 1c 的最小硬币。最多 4 美分，我们需要 1c 硬币，因为这是最小的面额。
2. 对于 5 美分，我们有一个 5c 硬币。结合上面的 4c，我们可以生成 1 到 9 之间的任何数字。
3. 对于 10 美分，我们需要 1 X 10c。结合以上三者，我们可以生成 1 到 19 之间的任意数字。
4. 对于 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}
构造 5ccell(2, 9) ==> 使用 {1c, 10c}
构造 9ccell(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 行中的最新面额。最好的选择就是您的答案。

该表实际上记住了较小问题的解决方案，因此您无需一次又一次地解决它们。