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
Vous devez vous connecter pour publier un commentaire.
Supposons tous vos
ni
sont1
.Laisser
ways[j] = number of ways of obtaining sum j
.Vous pouvez calculer ce comme (c'est ce que vous faites, mais je ne sais pas pourquoi vous avez nommé votre variable
primes
).Cela signifie que vous n'utilisez que chaque pièce de monnaie de valeur
Xi
une fois. Vous pouvez ajouter une autre boucle de l'utiliser au moins une fois et au plusni
fois cependant:Vous pouvez toujours demander à votre modulo et de calculer votre limite, j'ai laissé ceux pour des raisons de simplicité.
Pouvez-vous nous expliquer cette réponse? J'ai eu de pièce de monnaie de problème de changement de travail, mais de la difficulté lorsque les pièces sont limitées par exemple, 1p = 6 pièces, 2p = 10 pièces, etc.
Je crois que la boucle j doivent être remplis dans l'ordre croissant puisque vous êtes à la recherche à la précédente façons[j]. Suis-je la corriger?
non, parce qu'alors, dans la même itération, vous utilisiez déjà des valeurs calculées, en utilisant éventuellement les
Xi
fois de plus que permis.OriginalL'auteur IVlad
Le problème est nommée "La pièce de problème" et est connu pour être NP-difficile.
Vous pouvez en apprendre un peu plus sur elle ici.
Il a également dit Un ami m'a dit que c'est une variante du problème de sac-à-dos, mais je ne sais pas comment faire. Le problème a un nom, et a été beaucoup étudié. Ce n'est pas un jouet problème.
cela peut être vrai, mais ce n'est certainement pas ce que vous avez lié.
Je pense qu'il est. Si le PGCD est plus grand que 1, il y a plus de solutions, vous pouvez obtenir trivialement en utilisant des sous-multiples. (c'est à dire remplacer un de 10 $pièce en deux $5 pièces). Mais vous devez d'abord résoudre le problème difficile. Il suffit de retirer le non PGCD=1 pièces, de résoudre le problème, puis ajouter les combinaisons où vous pouvez farcir le plus grand nombre de dénominations (non PGCD =1)
Le problème semble lié à environ
largest nonrepresentable amounts
- je n'ai pas la connexion àhow many ways can we obtain $X
. (Il mentionneNo closed-form solution is known [generally]
, qui, combiné avec votreknown to be NP-hard
ci-dessus me fait me demander: Êtes-vous en pensant à la droite de problème, mais en fournissant un lien vers un (vaguement) liés, mais différents?)OriginalL'auteur Dr. belisarius