Pièce de monnaie de changer avec le nombre limité de pièces de monnaie

J'ai écrit un programme pour générer des sous-ensemble de la somme qui pourrait être utilisé dans ce problème qui stipule:

Supposons que, vous disposez de 3 $1-pièces, 2
$2-pièces, 3 $à 5 pièces, 1 $10-pièce,
il y a 4 façons d'obtenir de $10 à partir de
ces pièces. Si il y a n1 $X1
les pièces de monnaie, n2 $X2 pièces.... nm $Xm pièces de monnaie,
de combien de façons peut-on obtenir $X à partir de
ces nombre limité de pièces de monnaie?

Si nous créons un ensemble de { X1, X1,..... X1, X2, X2.......... X2, ..., ..., ............, Xm, Xm..., Xm}, puis exécutez sous-ensemble de sommation sur elle, nous pouvons certainement obtenir un résultat de $X.
Mais je ne pouvais pas trouver un moyen d'utiliser les ensembles {n1, n2, n3.... nm} , {X1, X2, X3.... Xm}.
Un ami m'a dit que c'est une variante du problème de sac-à-dos, mais je ne sais pas comment.

Partielle de code de ce que j'ai écrit :

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

Qu'il serait intéressant pour moi, si vous avez la gentillesse de nous expliquer un peu minutieusement.

MODIFIER:
Cette question est plus approprié pour stackexchange pour l'informatique, mais depuis c'est une vieille question de la mienne, je suis plutôt d'édition ici.

Ce problème peut être résolu avec Inclusion Exclusion principe, et il vient à portée de main quand nous avons des valeurs de pièce fixe, mais le nombre de chaque pièce variant avec chaque requête.

Supposons que, façons[v] est des façons de faire de $v avec $x1, $x2, .. $xm, chaque être utilisé autant de fois que nécessaire. Maintenant, si nous utilisons seulement n1 nombre de $x1, nous devons soustraire les configurations à l'aide d'au moins (n1 + 1) nombre de $x1 ( qui est en fait façons[v - (n1 + 1)x1] ). En outre, si nous utilisons seulement n2 nombre de $x2, nous devons soustraire façons[v - (n2 + 1)x2] ainsi, et etc.

Maintenant, nous avons deux fois soustrait les configurations où au moins (n1 + 1) $x1 et (n2 + 1) $x2 sont utilisées, donc nous avons besoin d'ajouter façons[v -(n1 + 1)x1 - (n2 + 1)x2] et etc.

En particulier, si,

N = ensemble de configurations où toutes les pièces sont utilisées autant que possible,

Ai = ensemble de configurations où au moins ni + 1 nombres de $xi est utilisé, pour 1 <= je <= m, puis

le résultat que nous cherchons = |N| - |A1| - |A2| .. - |Suis| + |A1 et A2| + |A1 et A3| + ... - |A1 et A2 et A3| .....

Le code qui calcule le nombre de configurations avec un nombre illimité de pièces de monnaie est en fait plus simple:

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

OriginalL'auteur sarker306 | 2010-11-16