Coin change with limited number of coins

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

回答1:

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.

回答2:

The problem is named "The coin problem" and is known to be NP-hard.

You may learn a little about it here.