硬币找零问题（有限硬币数量）

Question

我写了一个生成子集和的程序，可以用于解决以下问题：

假设你有3个1美元硬币、2个2美元硬币、3个5美元硬币和1个10美元硬币，那么有4种方法可以从这些硬币中获得10美元。如果有n1个X1硬币、n2个X2硬币... nm个Xm硬币，我们可以用这些有限数量的硬币获得多少种方法来获得X美元呢？

如果我们创建一个集合{X1，X1 ..... X1，X2，X2 .......... X2，......，......，............，Xm，Xm ... Xm}，然后在其上运行子集求和，我们肯定可以得到X美元的结果。但我找不到使用集合{n1，n2，n3 ... nm}，{X1，X2，X3 ... Xm}的方法。一位朋友告诉我这是背包问题的变体，但我不确定如何解决。

这是我所写代码的一部分：

ways[0]=1, mylim=0;
for(i=0;i<count;i++){
    if(mylim+coins[i]<=LIMIT) mylim+=coins[i];
    else mylim=LIMIT;

    for(j=mylim; j>=coins[i];j--){
        ways[j]=(ways[j]+ways[j-coins[i]])%MOD;
    }
}

如果您能详细解释一下，那就太好了。 编辑： 这个问题更适合计算机科学的stackexchange，但由于这是我的一个旧问题，我宁愿在这里进行编辑。 使用包含排除原理可以解决这个问题，在每个查询中硬币价值固定但每种硬币数量不同时非常方便。假设，ways[v]表示用$x1$，$x2$，... $xm$制作$v$的方法，每个方法被使用多次。现在，如果我们只使用$n1$个$x1$数，则必须减去至少使用（$n1$ + 1）个$x1$的配置（实际上是ways[v - (n1 + 1)x1]）。此外，如果我们只使用$n2$个$x2$数，则还必须减去ways[v - (n2 + 1)x2]，以此类推。现在，我们两次减去了至少使用（$n1$ + 1）$x1$和（$n2$ + 1）$x2$的配置，因此我们需要添加ways[v -(n1 + 1)x1 - (n2 + 1)x2]等。特别地，如果， N = 使用尽可能多的所有硬币的配置集，Ai = 至少使用ni+1个$xi$的配置集，对于1<=i<=m，则我们要寻找的结果= |N| − |A1| −| A2| ... - |Am| + | A1和A2| + | A1和A3| + ... - | A1和A2和A3| ... 计算具有无限硬币数量的配置数的代码实际上更简单：

ways[0]=1;
for( int i = 0 ; i < count ; i++){
    for( int j = coins[i] ; j < ways.size() ; j++ ){
        ways[j] += ways[j-coins[i]];
    }
}

- sarker306

Answer 1

假设所有的 ni 都是 1。

令 ways[j] = 获得和为 j 的方式数。

您可以按以下方式计算这个值（这就是您正在做的事情，但我不知道为什么您将变量命名为 primes）。

ways[0] = 1
for i = 1 to m do
    for j = myLim downto X[i] do
        ways[j] += ways[j - X[i]];

这意味着您只能使用每个价值为Xi的硬币一次。您可以添加另一个循环，使其至少使用一次且最多ni次：

ways[0] = 1
for i = 1 to m do
    for times = 1 to n[i] do // use Xi one time, then two times, then three, ..., then ni
        for j = myLim downto times*X[i] do
            ways[j] += ways[j - times*X[i]];

为了简洁，本文省略了取模和计算极限的步骤。您仍然可以应用这些步骤。

- IVlad

---

嗯，使用质数很容易解释为什么。我从一个要求质数价值硬币的代码中复制了它。:P。而使用“times”是没有帮助的...我想我刚刚做到了这一点，但它的答案比平常更大。正如MathWorld所说，需要GCD...我正在尝试扩展这个想法。非常感谢你的回答 :)。 - sarker306

请您能否进一步解释这个答案？我已经解决了硬币找零问题，但当硬币数量有限时，如1便士=6枚硬币，2便士=10枚硬币等，我遇到了麻烦。 - adi

我认为 j 循环应该按递增顺序填充，因为您正在查看以前的 ways[j]。我正确吗？ - marti

@marti 不行，因为这样在同一次迭代中，你会使用已经计算出来的值，可能会使用 Xi 比允许的次数多。 - IVlad

Answer 2

这个问题被称为“硬币问题”，已知是NP难问题。

你可以在这里了解一些相关信息。

- Dr. belisarius

---

我不明白那与此有何关联。楼主的问题中并未提到最大公约数，而是询问另一件事情。 - IVlad

@IVlad他还说：“一个朋友告诉我这是背包问题的一种变化，但我不确定。” 这个问题有一个名称，并且已经被广泛研究，它不是一个玩具问题。 - Dr. belisarius

可能是这样，但绝对不是你链接的内容。 - IVlad

@IVlad 我认为是这样的。如果GCD大于1，则有更多解决方案，可以通过使用子倍数轻松获得（例如，用两个5美元硬币替换10美元硬币）。但是您首先必须解决难题。只需删除非GCD = 1的硬币，解决问题，然后添加那些您可以填充更高面额（非GCD = 1）的组合即可。 - Dr. belisarius

看起来这个相关问题似乎是关于“最大不可表示金额”的 - 我不明白和“我们有多少种方法可以获得X”之间的联系。(它提到“通常没有已知的封闭解决方案”，结合你上面的“已知为NP难问题”，让我问：你是否考虑了正确的问题，但提供了一个（松散）相关但不同的链接？) - greybeard