硬币数量有限的硬币找零

Question

我写了一个生成子集总和的程序，它可能会用在这个问题中，它指出:

Suppose, you have 3 $1-coins, 2 $2-coins, 3 $5-coins, 1 $10-coin, there are 4 ways to obtain $10 from those coins. If there are n1 $X1 coins, n2 $X2 coins.... nm $Xm coins, how many ways can we obtain $X from these limited number of coins?

如果我们创建一组 { X1, X1..... X1, X2, X2....... X2, ..., ..., ...... ....., Xm, Xm... Xm}，然后对其进行子集求和，肯定可以得到$X的结果。但是我找不到使用集合 {n1, n2, n3.... nm} , {X1, X2, X3.... Xm} 的方法。一个 friend 告诉我这是背包问题的变体，但我不确定，如何。

这是我写的部分代码:

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 制作$v 的方法， .. $xm，每个都根据需要使用多次。现在，如果我们只使用 n1 个 $x1，我们必须使用至少 (n1 + 1) 个数来减去配置$x1(实际上是方式[v - (n1 + 1)x1])。此外，如果我们只使用 n2 个 $x2，我们必须减去 ways[v - (n2 + 1) x2] 以及等等。

现在，我们两次减去至少 (n1 + 1) $x1 和 (n2 + 1) $x2 被使用，因此我们需要添加方式[v -(n1 + 1)x1 - (n2 + 1)x2] 等。

特别是，如果，

N = 尽可能多地使用所有硬币的配置集，

Ai = 一组配置，其中至少使用了 ni + 1 个 $xi，对于 1 <= i <= m，然后

我们求的结果= |N| - |A1| - |A2| .. - |是| + |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]];
    }
}

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]];

这意味着您只能使用每枚值(value) 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]];

您仍然可以应用您的模数并计算您的限制，为了简单起见，我将它们省略了。