C++ Teil des Brute-Force-Rucksacks

Question

Leser, Nun, ich denke, ich habe gerade ein wenig gehirn gefickt. Ich implementiere Rucksack, und ich dachte darüber nach, ich implementierte Brute-Force-Algorithmus wie 1 oder 2 mal. Also habe ich beschlossen, noch eins zu machen. Und hier ist, was ich in chocked.

Lassen Sie uns entscheiden, W ist das maximale Gewicht, und w (min) ist minimal-Gewicht Element können wir in Rucksack wie k=W/w(min) mal. Ich erkläre das, weil Sie, Leser, besser wissen, warum ich meine Frage stellen muss.

Jetzt. Wenn wir uns vorstellen, dass wir 3 Arten von Dingen haben, die wir in den Rucksack stecken können, und unser Rucksack kann 15 Masseneinheiten speichern, zählen wir jedes Stückgewicht als seine Zahl. Wir können also 15 Dinge vom 1. Typ oder 7 Dinge vom 2. Typ und 1 vom 1. Typ platzieren. aber Kombinationen wie 22222221[7ed] und 12222222[7ed] werden für uns dasselbe bedeuten. und sie zu zählen ist eine Verschwendung jeglicher Art von Ressourcen, die wir für die Entscheidung bezahlen. (Es ist ein Witz, weil bf eine Verschwendung ist, wenn wir einen billigeren Algorithmus haben, aber ich bin sehr interessiert)

Wie ich denke, die Art der Auswahlen, die wir durch alle möglichen Kombinationen durchlaufen müssen, heißt "Kombinationen mit Wiederholungen ". Die Nummer C'(n,k) zählt als (n+k-1)!/(n-1)!k!. (während ich meine Nachricht eintippte, habe ich gerade ein Loch in meiner Theorie entdeckt. Wir werden wahrscheinlich ein leeres, Null-gewichtet-Null-Preis-Element hinzufügen müssen, um es frei zu halten.)

so , Was ist los.

https://rosettacode.org/wiki/Combinations_with_repetitions

wie dieses Problem ist gut beschrieben hier oben^Ich will nicht wirklich Stapel auf diese Weise verwenden, möchte ich Variationen in einzelnen Zyklus erzeugen, die from i=0 to i<C'(n,k) geht.

also, wenn ich es schaffen kann, wie es funktioniert?

Maske, Straße - ist ein Array von Indizes, die jeweils von 0 bis n gleich sein können; und müssen erzeugt werden als C '(n, k) (siehe oben) von {0, 1, 2, ..., n} durch k Elemente in jeder Auswahl (Kombination mit Wiederholungen, bei denen die Reihenfolge unwichtig ist)

das ist es. beweise mich falsch oder hilf mir. Vielen Dank im Voraus _

und ja, natürlich Algorithmus wird die Hölle viel Zeit nehmen, aber es sieht aus wie es sollte funktionieren. und ich bin sehr interessant darin.

UPDATE:

was ich vermisse?

http://pastexen.com/code.php?file=EMcn3F9ceC.txt

Answer 1

Die Antwort von Minoru https://gist.github.com/Minoru/745a7c19c7fa77702332cf4bd3f80f9e hier zur Verfügung gestellt wurde, es reicht nur das erste Element zu erhöhen, dann zählen wir alle der Überträge, gesetzt, wo wir einen Übertrag haben und Reset-Wert als die maximale Anzahl von Elemente zum Zurücksetzen und Zurücksetzen damit.

hier ist mein Code:

#include <iostream> 

using namespace std; 
static long FactNaive(int n) 
{ 
    long r = 1; 
    for (int i = 2; i <= n; ++i) 
     r *= i; 
    return r; 
} 
static long long CrNK (long n, long k) 
{ 
    long long u, l; 
    u = FactNaive(n+k-1); 
    l = FactNaive(k)*FactNaive(n-1); 
    return u/l; 
} 

int main() 
{ 
    int numberOFchoices=7,kountOfElementsInCombination=4; 
    int arrayOfSingleCombination[kountOfElementsInCombination] = {0,0,0,0}; 
    int leftmostResetPos = kountOfElementsInCombination; 
    int resetValue=1; 

    for (long long iterationCounter = 0; iterationCounter<CrNK(numberOFchoices,kountOfElementsInCombination); iterationCounter++) 
    { 
     leftmostResetPos = kountOfElementsInCombination; 

     if (iterationCounter!=0) 
     { 
      arrayOfSingleCombination[kountOfElementsInCombination-1]++; 
      for (int anotherIterationCounter=kountOfElementsInCombination-1; anotherIterationCounter>0; anotherIterationCounter--) 
      { 
       if(arrayOfSingleCombination[anotherIterationCounter]==numberOFchoices) 
       { 
        leftmostResetPos = anotherIterationCounter; 
        arrayOfSingleCombination[anotherIterationCounter-1]++; 
       } 
      } 
     } 

     if (leftmostResetPos != kountOfElementsInCombination) 
     { 
      resetValue = 1; 

      for (int j = 0; j < leftmostResetPos; j++) 
      { 
       if (arrayOfSingleCombination[j] > resetValue) 
       { 
        resetValue = arrayOfSingleCombination[j]; 
       } 
      } 

      for (int j = leftmostResetPos; j != kountOfElementsInCombination; j++) 
      { 
       arrayOfSingleCombination[j] = resetValue; 
      } 
     } 

     for (int j = 0; j<kountOfElementsInCombination; j++) 
     { 
      cout<<arrayOfSingleCombination[j]<<" "; 
     } 
     cout<<"\n"; 

    } 

    return 0; 
} 

dank viel, Minoru