硬币找零硬币数量有限 [英] Coin change with limited number of coins

问题描述

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

  

假设，你有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}。 一个朋友告诉我，这是背包问题的变化，但我不知道，怎么样。

这是我自己编写的部分code：

 办法[0] = 1，mylim = 0;
对于（i = 0; I＆LT;计数;我++）{
    如果（mylim +硬币[1]  - ; = LIMIT）mylim + =硬币[I];
    否则mylim =限制;

    为（J = mylim; J＆GT; =币[I]的J  - ）{
        方法[J] =（方法[J] +方法[J-币[I]）％MOD;
    }
}
 

如果你还跟精心解释一下这将是非常适合我。

修改： 这个问题是比较适合stackexchange计算机科学，但因为它是我的一个老问题，我宁愿编辑在这里。

此问题可能是入选排除的原则来解决，它来得心应手的的时候，我们有固定的硬币值，但每个查询的每个硬币的数量变化的

假设，办法[V] 的是制造方式的 $ V 的用的 $ X1 的 $ X2 的， .. $ XM 的，根据需要各自被使用多次。现在，如果我们只使用的 N1 的的的 $ X1 的数字，我们必须减去使用的配置至少（ N1 的+ 1）的数 $ X1 的（这实际上是的办法的[ v - 输出（N1 + 1）×1 的]）。此外，如果我们只使用的 N2 的的的 $ X2 的，我们有一个数字减去的办法的[ v - 输出（N2 + 1） X2 的]还有，等。

现在，我们已经两次减去的配置，其中至少有（ N1 的+ 1）的 $ X1 的和（ N2 的+ 1）的 $ X2 的使用，因此我们需要添加的办法的[ v - 输出（N1 + 1）×1 - （N2 + 1）×2 的]等。

在具体地，如果

N =组配置，所有的硬币都是用尽可能多的，

爱 =组配置，其中至少 NI 的+ 1号的 $曦的时，1＆LT; = 我的＆LT; = M 的，那么

我们正在寻找的结果= | N | - | A1 | - | A2 | .. - | （上午） | + | A1 和 A2 | + | A1 和 A3 | + ... - | A1 和 A2 和 A3 | ......

在code的计算与无限硬币的配置数量实际上是简单的：

 办法[0] = 1;
的for（int i = 0; I＆LT;计数;我++）{
    对于（INT J =硬币[我]; J＆LT; ways.size（）; J ++）{
        方法[J] + =方法[J-币[I]];
    }
}
 

解决方案

让我们假设你所有的 NI 是 1 。

让方法[J] =的获取和J的方式数。

您可以计算这个像这样（这是你在做什么，但我不知道为什么你叫你的变量素数）。

 办法[0] = 1
对于i = 1到m做
    对于j = myLim DOWNTO X [I]做
        方法[J] + =方法[J  -  X [I]];
 

这意味着你只使用值的每个硬币曦键。您可以添加另一个循环至少一次，至多 NI 次但使用它：

 办法[0] = 1
对于i = 1到m做
    对于时间= 1到n [I]做//使用习一次，然后两次，然后三，...，然后妮
        对于j = myLim DOWNTO倍* X [I]做
            方法[J] + =方法[J  - 次* X [I]];
 

您仍然可以申请你的模数，并计算你的极限，我离开了那些对简便性。

I have written a program for generating subset sum which might be used in this problem which states:

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?

If we create a set of { X1, X1..... X1, X2, X2.......... X2, ..., ..., ............, Xm, Xm... Xm}, and then run Subset summing on it, surely we can get a result for $X. But I could not find a way to use the sets {n1, n2, n3.... nm} , {X1, X2, X3.... Xm}. A friend told me that it is a variation of knapsack problem, but I am not sure, how.

This is a partial code of what I have written :

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

It would be great for me if you are kind enough to explain a bit elaborately.

EDIT: This question is more suitable for stackexchange for computer science, but since it is an old question of mine, I'm rather editing it here.

This problem can be solved with Inclusion Exclusion principle, and it comes handy when we have coin values fixed but number of each coin varying with each query.

Suppose, ways[v] is ways of making $v with $x1, $x2, .. $xm, each being used as many times as needed. Now, if we are using only n1 numbers of $x1, we have to subtract the configurations using at least (n1 + 1) numbers of $x1 ( which is actually ways[v - (n1 + 1)x1] ). Moreover, if we are using only n2 numbers of $x2, we have to subtract ways[v - (n2 + 1)x2] as well, and etc.

Now, we have twice subtracted the configurations where at least (n1 + 1) $x1 and (n2 + 1) $x2 are used, hence we need to add ways[v -(n1 + 1)x1 - (n2 + 1)x2] and etc.

In particular, if,

N = set of configurations where all coins are used as many as possible,

Ai = set of configurations where at least ni + 1 numbers of $xi is used, for 1 <= i <= m, then

the result we are seeking = |N| - |A1| - |A2| .. - |Am| + |A1 and A2| + |A1 and A3| + ... - |A1 and A2 and A3| .....

The code which computes number of configurations with unlimited coins is actually simpler:

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

解决方案

Let's assume all your ni are 1.

Let ways[j] = number of ways of obtaining sum j.

You can compute this like so (this is what you're doing, but I don't know why you named your variable primes).

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

This means you only use each coin of value Xi once. You can add another loop to use it at least once and at most ni times however:

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

You can still apply your modulo and compute your limit, I left those out for simplicity.

这篇关于硬币找零硬币数量有限的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！