硬币的数量有限硬币找零

Question

我写了一个程序产生可能在这个问题其中规定可以使用子集和：

假设，你有3个$ 1的硬币，2 $ 2硬币，3 $ 5硬币，1 $ 10的硬币中，有4种方式获得那些硬币$ 10。如果有N1 $ X1硬币，N2 $ X2硬币....纳米$ XM硬币，有多少种方法，我们可以从硬币的这些数量有限的获得$ X？

如果我们建立一个集合{X1，X1 ..... X1，X2，X2的.......... X2，...，...，.......... ..，XM，XM ... XM}，然后运行子集相加就可以了，我们肯定可以得到$ X的结果。但我不能找到一种方法，使用集{N1，N2，N3 ....纳米}，{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计算机科学，但因为它是我的一个老问题，我愿意在这里编辑它。

这个问题可以通过容斥原理来解决，它来得心应手，当我们有固定的硬币值，但每个查询的不同每个硬币的数量。

假设，方法[V]为使$ V以$ X1，X2 $，.. $ XM的方式，根据需要每个被使用多次。现在，如果我们使用的$ X1只有n1个，我们必须减去至少使用（N1 + 1）号码$ X1的配置（这实际上是方法[V - （N1 + 1）×1]）。此外，如果我们只使用$ X2 n2个，我们要减的方式[V - （N2 + 1）×2]，以及，等

现在，我们已经两次减去其中至少使用（N1 + 1）$ x1和（N + 1）$ X2的配置，因此我们需要补充的方式[V - （N1 + 1）×1 - （N2 + 1） X2]等。

特别是，如果，

N =组，其中所有的硬币被用于尽可能多的配置中，

其中至少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] = number of ways of obtaining sum 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]];

你仍然可以申请你的模并计算你的极限，我离开了那些为了简单起见。

Answer 2

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

你可能知道一些关于它here.