硬币更换问题与每个面额的无限数量的硬币

Question

我想知道硬币变化问题的算法的想法,其中每个面额具有infinte数量的硬币.意味着如何应用DP(如标准硬币更换问题)例如在套装1,10,15中,更改为35给出 - 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)==> 5c仅使用{1c}
cell(2, 9)==>构造9c使用{1c, 10c}
cell(3, 27)==>构造27c使用构造{1c, 10c, 15c}
现在你的目标是得到答案cell(x, n)

Solution:
从最简单的问题开始解决这个问题.解决第一行是微不足道的,因为在第一行中唯一可用的面额是{1c}.第1行中的每个单元格都有一个简单的解决方案,导致cell(1, n)= {nx1c}(n硬币1c).

现在进入下一行.推广第二行,让我们看看如何解决(比如说)cell(2, 28)构建28c使用{1c, 10c}.在这里,您需要做出决定,是否包括10c在解决方案中,以及多少硬币.你有3个选择(3 = 28/10 + 1)

Choice 1:从上一行(存储在其中)中
取出{1x10c}剩下的部分cell(1, 18).这给你{1x10c, 18x1c}=19 coins

Choice 2:从上一行(存储在其中)中
取出{2x10c}和休息cell(1, 8).这给你{2x10c, 8x1c}=10 coins

Choice 3:
取10c上一行中的其余部分(存储在其中cell(1, 28)).这给你{28x1c}=28 coins

显然,选择2是最好的,因为它需要更少的硬币.将其写在表格中并继续.该表将一次填充一行,并且按行增加的顺序排成一行.

按照上述规则,您将达到cell(x, n),解决方案将是n/p + 1替代品之间的选择,其中p=最新面额的行x.最好的选择是你的答案.

该表实际上记住了解决较小问题的解决方案,因此您不需要一次又一次地解决它们.