Stacking und Dynamische Programmierung

Question

Grundsätzlich Ich versuche, dieses Problem zu lösen:

Da N Einheitswürfel Blöcke, finden die kleinere Anzahl von Pfählen zu machen, um alle Blöcke zu verwenden. Ein Stapel ist entweder ein Würfel oder eine Pyramide. Zum Beispiel sind zwei gültige Stapel der Würfel 4 * 4 * 4 = 64 mit 64 Blöcken und die Pyramide 1² + 2² + 3² + 4² = 30 mit 30 Blöcken.

Allerdings kann ich nicht den richtigen Winkel finden, um es zu nähern. Ich habe das Gefühl, dass es dem Rucksackproblem ähnlich ist, konnte aber keine Implementierung finden.

Jede Hilfe wäre sehr willkommen!

Answer 1

Zuerst gebe ich eine Wiederholungsbeziehung, die es erlaubt, das Problem rekursiv zu lösen. Angesichts N, lassen

SQUARE-NUMS 
TRIANGLE-NUMS 

sein die Teilmenge von Quadratzahlen und Dreieckszahlen in {1,...,N} sind. Lassen Sie PERMITTED_SIZES die Vereinigung von diesen sein. Man beachte, dass, da 1 in PERMITTED_SIZES auftritt, jeder Fall möglich ist und ein nichtnegatives Optimum ergibt.

Die folgende Funktion in Pseudocode löst das Problem in der Frage rekursiv.

int MinimumNumberOfPiles(int N) 
{ 
    int Result = 1 + min { MinimumNumberOfPiles(N-i) } 
    where i in PERMITTED_SIZES and i smaller than N; 
    return Result; 
} 

Die Idee ist, eine zulässige Binabmessung für die Elemente zu wählen, entfernen Sie diese Elemente und lösen rekursiv für die kleineren Instanzen (die die Probleminstanz kleiner macht). Um die dynamische Programmierung zu verwenden, um mehrere Auswertungen desselben Teilproblems zu umgehen, würde man einen eindimensionalen Zustandsraum verwenden, nämlich ein Feld A[N], wobei A[i] die minimale Anzahl von Pfeilen ist, die für Einheitenblöcke i benötigt werden. Unter Verwendung dieses Zustandsraums kann das Problem wie folgt iterativ gelöst werden.

for (int i = 0; i < N; i++) 
{ 
    if i is 0 set A[i] to 0, 
    if i occurs in PERMITTED_SIZES, set A[i] to 1, 
    set A[i] to positive infinity otherwise; 
} 

Dies initialisiert die Zustände, die zuvor und entsprechen den Basis Fällen in der obigen Rekursion bekannt sind. Als nächstes werden die fehlenden Zustände mit der folgenden Schleife gefüllt.

for (int i = 0; i <= N; i++) 
{ 
    if (A[i] is positive infinity) 
    { 
     A[i] = 1 + min { A[i-j] : j is in PERMITTED_SIZES and j is smaller than i } 
    } 
} 

Der optimale Wert gewünscht wird in A[N] gefunden werden. Beachten Sie, dass dieser Algorithmus nur die Mindestanzahl von Pfählen berechnet, nicht aber die Pfähle selbst; Wenn eine geeignete Partition benötigt wird, muss sie entweder durch Zurückverfolgen oder durch Beibehalten zusätzlicher Hilfsdatenstrukturen gefunden werden.

Insgesamt vorausgesetzt, dass PERMITTED_SIZES bekannt ist, kann das Problem in O(N^2) Schritten gelöst werden, wie PERMITTED_SIZES höchstens N Werte enthält.

Das Problem kann als eine Anpassung des Rod Cutting Problem gesehen werden, wobei jedes Quadrat oder Dreieck Größenwert hat 0 und jede andere Größe hat Wert 1, und das Ziel ist, den Gesamtwert zu minimieren.

Insgesamt sind zusätzliche Berechnungskosten erforderlich, um PERMITTED_SIZES aus dem Eingang zu generieren.

Genauer gesagt, die entsprechende Auswahl von Pfählen, einmal gefüllt A, kann mit Backtracking wie folgt generiert werden.

int i = N; // i is the total amount still to be distributed 
while (i > 0) 
{ 
    choose j such that 
    j is in PERMITTED_SIZES and j is smaller than i 
    and 
    A[i] = 1 + A[i-j] is minimized 
    Output "Take a set of size" + j; // or just output j, which is the set size 

    // the part above can be commented as "let's find out how 
    // the value in A[i] was generated" 

    set i = i-j; // decrease amount to distribute 
}