Berechnen, wie viele Bälle in Behältern über mehrere Werte mit dynamischer Programmierung

Question

In Bezug auf das klassische Problem der N identische Kugeln in M ​​verschiedenen Bins und Drucken aller Kombinationen: Was wäre, wenn Sie das Problem durch Drucken aller Fälle 0< M, N erweitern möchten Brute-Force-Methode so etwas wie dies geschehen könnte:

for (int i =0; i<M; i++) 
{ 
    for (int j =0; j <N; j++) 
    { 
     PrintAllCombinations(j,i) 
    } 
} 

Nun, wenn wir den Ausgang des ersten Paar m studieren und n, sehen wir, dass der Ausgang jeder vorherigen Iteration eine Teilmenge der nächsten ist. Es scheint mir, dass wir einen dynamischen Algorithmus anwenden können, um dieses Phänomen auszunutzen. Da wir jedoch immer noch alle n partitionieren müssen, zum Beispiel n=3 = 3 +0, 2+1, 1+2. Wir müssen immer noch viele redundante Kombinationsberechnungen machen.
Irgendwelche Ideen für Verbesserungen?

Answer 1

Lassen Sie S[i][j] die Anzahl der Kombinationen für i Bälle in j Bins sein.

S[0][j] = 1 für alle j, da die einzige Kombination ist, alle Bins leer zu haben.

S[i][1] = 1 für alle ich, da die einzige Kombination ist, alle Bälle in den einen Behälter zu legen.

Für jeden anderen i, j S[i][j] = sum(x = 0 -> i, S[i-x][j-1]). Das heißt für jede andere Position können Sie die Anzahl der Kombinationen berechnen, indem Sie jede mögliche Anzahl von Bällen der letzten Bin zuweisen und die Anzahl der Kombinationen addieren, die Sie erhalten.

Wenn Sie die Kombinationen ausdrucken möchten, können Sie die Anzahl durch die tatsächlichen Kombinationen ersetzen und den Wert x anfügen, wenn Sie die internen Kombinationen in der Summe verwenden. Das wird eine Menge Speicher benötigen ohne viel Geschwindigkeitsgewinn. Wiederholen Sie einfach die Rekursion und wiederholen Sie die Berechnung, da Sie ohnehin an die Anzahl der Lösungen gebunden sind.