dynamic-programming - 硬币变化的变化

Question

所以典型的硬币找零问题要求你弄清楚你是否可以使用无限的面额硬币 x1、x2、...、xn 来换取价值 v，但我想知道你如何才能弄清楚每个硬币最多使用一次同样的问题？

对于最初的问题，我知道您可以遍历值的前缀并查看是否可以为 v-x_i 进行更改，但是当它被限制为每个面额最多一个硬币时，我不知所措。

有什么建议可以让我开始吗？我可能在想你也可以迭代面额的前缀。虽然不确定...

score 0 · Accepted Answer

对于硬币找零问题，您可以使用前向或后向递归。在你的声明中，你使用了向后。这里我给出一个forward方法，它可以轻松解决UNLIMITED版本和AT-MOST-ONCE版本

假设 f 是一维布尔数组。f[i] 表示你是否可以对值 i 进行更改。最初，f[0]=true，其他等于 false。

无限版本：

for (int i=1;i<=n;i++)
    for (int j=0;j<v;j++)
        if (f[j])
            f[j+x[i]]=true;

最多一次版本：

for (int i=1;i<=n;i++)
    for (int j=v-1;j>=0;j--)
        if (f[j])
            f[j+x[i]]=true;

唯一的区别是循环 j 的顺序。

一个帮助你理解的例子：

假设只有一种硬币的价格为 2。即 x[1]=2。v=10

在第一个算法之后，你可以得到 f[0]=f[2]=f[4]=f[6]=f[8]=f[10]=true。

但是对于第二种算法，你只能得到 f[0]=f[2]=true。

score 0 · Accepted Answer

这个问题可以使用动态规划来解决。

我个人觉得画一张表来帮助推导算法很有用。下面是面额为 5、10、2、1 和总价值 V 的硬币的棕褐色示例表。

首先，如果 v = 0，我们为所有 i 初始化表为 True（对于零值，更改总是正确的）

For i: 0-> n D(v,0) = true

然后我们逐行（从左到右）逐列（从上到下）遍历表

For v: 1-> V For i: 0-> n

可以观察到，我们能够在两种情况下给出值 v 和硬币 xi 的变化：

D(v,i) = true if D(v-xi, i-1) = true

这种情况的示例包括硬币 xi=5（第二列）和 v=5 或硬币 xi=1（最后一列）和 v=6

D(v,i) = true if D(v, i-1) = true

这种情况的例子是第 5 行。

在上述情况均不适用的情况下，我们不能给予全额更改并且D(v,i)是错误的。最终的解决方案是与总值V和索引n对应的表格元素。

总结一下：

  For i: 0-> n D(v,0) = true

  For v: 1-> V
    For i: 0-> n

    D(v,i)= D(v, i-1) V D(v-xi, i-1 )
    else D(v,i) = false;

  return D(V, n)

2 回答 2