Coin change with limited number of coins

Question

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

Shurlocke

Answer 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.

Aphorism

Well, using primes is easy to explain why. I copied it from a code which asks for prime valued coin. :P . And using 'times' wont help... I think I did just that, but it ended with larger answer than usual. MAs MathWorld says, GCD is needed.... I am trying to extend the idea. Thanks a lot for your answer :). – Shurlocke

Can you please explain this answer further? I got coin change problem working but having trouble when the coins are limited e.g. 1p = 6 coins, 2p = 10 coins etc. – Traditor

I believe the j loop should be populated in an increasing order since you are looking at previous ways[j]. Am I correct? – Monarski

@Monarski no, because then, in the same iteration, you would be using already computed values, potentially using Xi more times than allowed. – Aphorism

Answer 2

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

You may learn a little about it here.

Porphyry

I don't see how that's related. The OP's question mentions no GCD and asks for something different. – Aphorism

@Aphorism He also says A friend told me that it is a variation of knapsack problem, but I am not sure, how. The problem has a name, and has been studied a lot. It's not a toy problem. – Porphyry

that may be so, but it's definitely not what you linked to. – Aphorism

@Aphorism I think it is. If the GCD is greater than 1 there are more solutions, you can get trivially by using sub-multiples. (i.e. replace a $10 coin by two $5 coins). But you have first to solve the hard problem. Just remove the non GCD=1 coins, solve the problem and then add those combinations where you can stuff up the higher denominations (non GCD =1) – Porphyry

The linked problem seems to be about largest nonrepresentable amounts - I don't get the connection to how many ways can we obtain $X. (It mentions No closed-form solution is known [generally], which, combined with your known to be NP-hard above makes me ask: Are you thinking of the right problem, but providing a link to a (loosely) related, but different one?) – Southerly