Algorithme pour calculer le nombre de combinaisons pour former 100

si vous devez diviser 100 Sur 2 avec une distance maximale de N, la valeur la plus basse dans la combinaison est

100 / 2-N / 2

si vous devez diviser 100 Sur 3 valeurs avec une distance maximale de N, cela devient plus délicat. La moyenne des 3 valeurs sera de 100/3, mais si l'une d'elles est beaucoup plus basse que cette moyenne, l'autre ne peut être que légèrement plus grande que cette moyenne, ce qui signifie que la valeur minimale n'est pas la moyenne moins le distance maximale divisée par deux, mais probablement

100 / 3-2N / 3

en général avec les valeurs M, cela devient

100 / M - (M-1) N / M

qui peut être simplifié par

(100 - (M-1) N) / M

de même, nous pouvons calculer la valeur la plus élevée possible:

(100 + (M-1)N) / M

Cela vous donne une fourchette pour la première valeur de votre combinaison.

pour déterminer la portée de la seconde valeur, vous devez considérer les contraintes suivantes:

• la distance avec la première valeur (ne doit pas être supérieur à la distance maximale)
• peut-on encore réaliser la somme (100)

La première contrainte est pas un problème. La seconde l'est.

supposons que nous divisons 100 Sur 3 avec une distance maximale de 30 en utilisant des multiples de 10 Calculé avant, la valeur minimale est:

(100 - (3-1)30) / 3 --> 13 --> arrondi au prochain multiple de 10 --> 20

La valeur maximale est de

(100 + (3-1)30) / 3 --> 53 --> arrondi au précédent multiple de 10 --> 50

donc pour la première valeur nous devrions itérer plus de 20, 30, 40 et 50.

supposons que nous choisissions 20. Il en reste 80 pour les 2 autres valeurs. Encore une fois nous pouvons distribuer 80 sur 2 valeurs avec une distance maximale de 30, ce qui donne:

Minimum: (80 - (2-1)30) / 2 --> 25 --> arrondi -- > 30

Maximum: (80 + (2-1)30) / 2 --> 55 --> arrondi -- > 50

La deuxième contrainte est que nous ne voulons pas d'une distance supérieure à 30 par rapport à notre première valeur. Cela donne un minimum de 10 et un maximum de 50.

maintenant, prendre L'intersection entre les deux domaines -- > 30 à 50 et pour la deuxième valeur iterate plus de 30, 40, 50.

alors répétez ceci pour la valeur suivante.

EDIT: J'ai ajouté l'algorithme en pseudo-code pour le rendre plus clair:

calculateRange (vector, remainingsum, nofremainingvalues, multiple, maxdistance)
{
if (remaingsum==0)
   {
   // at this moment the nofremainingvalues should be zero as well
   // found a solution
   print vector
   return;
   }

minvalueaccordingdistribution = (remainingsum-(nofremainingvalues-1)*maxdistance)/nofremaingvalues;
maxvalueaccordingdistribution = (remainingsum+(nofremainingvalues-1)*maxdistance)/nofremaingvalues;

minvalueaccordingdistance = max(values in vector) - maxdistance;
maxvalueaccordingdistance = min(values in vector) + maxdistance;

minvalue = min (minvalueaccordingdistribution, minvalueaccordingdistance);
maxvalue = max (minvalueaccordingdistribution, minvalueaccordingdistance);

for (value=minvalue;value<=maxvalue;value+=multiple)
   {
   calculaterange (vector + value, remainingsum - value, nofremainingvalues-1, multiple, maxdistance);
   }
}

main()
{
calculaterange (emptyvector, 100, 2, 20);
}

pourquoi ne pouvez-vous pas utiliser une approche de force brute avec peu d'optimisation? Par exemple, dire N-Nombre de combinaisons M-Multiples D-Max Distance possible

ainsi les valeurs possibles dans les combinaisons peuvent être M, 2M, 3M et ainsi de suite. Vous devez générer cet ensemble, puis commencer avec le premier élément de l'ensemble et essayer de trouver les deux suivants à partir du choix des valeurs de même ensemble (à condition qu'ils doivent être moins que D à partir de la première/deuxième valeur). Donc avec i / p de 3-10-30 serait

1. créer un ensemble de 10, 20, 30, 40, 50, 60, 70, 80, 90 comme une valeur possible
2. Démarrer avec 10, le choix de deuxième valeur doit être de 20, 30, 40, 50 (D < 30)
3. maintenant, choisissez la deuxième valeur de l'ensemble de 20, 30, 40, 50 et essayer d'obtenir la valeur suivante et ainsi de suite

si vous utilisez une récursion alors la solution deviendrait encore plus simple.

1. vous devez trouver N valeurs à partir d'un liste des valeurs possibles en MIN & MAX index.
2. alors essayez la première valeur à Indice MIN (à l'indice MAX). Dire que nous ont choisi la valeur à l'index X.
3. Pour chaque première valeur, essayez de trouver sortie des valeurs N - 1 de la liste où MIN = X + 1 et MAX.

la pire performance se produit lorsque M = 1 et N est suffisamment grand.

Est la distance entre les facteurs additifs, ou entre ? Par exemple, avec 3-10-20, est [20-40-60] une réponse valable? Je suppose que le dernier, mais la solution ci-dessous peut être modifié assez trivialement pour travailler pour le premier.

quoi qu'il en soit, le chemin à suivre est de commencer par la réponse la plus extrême (d'une sorte) que vous pouvez gérer, puis de suivre les réponses jusqu'à ce que vous arrivez à l'autre plus extrême.

faisons essayez de placer des chiffres aussi bas que possible, sauf pour la dernière, qui sera aussi haut que possible (étant donné que les autres sont faibles). Que le diviseur commun soit d et diviser 100 par elle, donc nous avons S = 100/d. Cela quantifie bien notre problème. Maintenant que nous avons notre contrainte que l'espacement est au plus s, sauf que nous allons convertir un certain nombre de quantifiée étapes, n = s/d. Supposons maintenant que nous avons M échantillons, i1...iM et écrire les contraintes:

i1 + i2 + i3 + ... + iM = S
0 <= i1 <= n
0 <= i2 <= n
. . .
0 <= iM <= n
i1 <= i2
i2 <= i3
. . .
i(M-1) <= iM

nous pouvons résoudre la première équation pour obtenir iM compte tenu des autres.

maintenant, si nous rendons tout aussi similaire que possible:

i1 = i2 = ... = iM = I
M*I = S
I = S/M

très bien--nous avons notre point de départ! (Si I est une fraction, faire les premiers I et le reste I+1.) Maintenant nous essayons juste de descendre chaque variable tour à tour:

for (i1 = I-1 by -1 until criteria fails)
  sum needs to add to S-i1
  i2 >= i1
  i2 <= i1 +n
  solve the same problem for M-1 numbers adding to S-i1
  (while obeying the above constraint on i2)

eh Bien, regardez ici--nous avons un algorithme récursif! On passe en revue et on lit les réponses.

bien sûr, nous pourrions marcher i1 vers le haut au lieu de vers le bas. Si vous avez besoin d'imprimer les réponses, autant le faire. Si vous avez juste besoin de les Compter, notez que Compter vers le haut est symétrique, donc doublez juste la réponse que vous obtenez de compter vers le bas. (Vous aurez aussi un facteur de correction si toutes les valeurs ne sont pas lancées de la même façon--si certaines étaient I et certains ont été I+1, vous devez en tenir compte, ce que je ne ferai pas ici.)

Edit: si la plage est ce que chaque valeur doit correspondre à l'intérieur, au lieu de tous les

0 <= i1 <= n

conditions, vous avez

max(i1,i2,...,iM) - min(i1,i2,...,iM) <= n

mais cela donne la même condition récursive, sauf que nous passons le long des max ET min de ces éléments que nous avons déjà sélectionné pour jeter dans le mix, au lieu d'ajouter une contrainte sur i2 (ou au tour de n'importe quelle autre variable).

Entrée: (2-10-20)

1. divisez le nombre par 1

(50,50)

2 Vérifier si la règle de différence permet cette combinaison. Si cela blesse la règle, puis arrêter, si cela permet, puis ajouter ceci et c'est des combinaisons à la liste de résultats

Par exemple: abs(50-50)<20, donc c'est ok

3 Augmenter la première valeur de param 2, diminuer la seconde valeur de param 2

4. 2. point