Box Stapel Problem

Question

Ich fand dieses berühmte dp Problem in vielen Orten, aber ich kann nicht herausfinden, wie zu lösen.

  

Sie sind eine Reihe von n Typen gegeben von   rechteckiges 3-D-Boxen, in dem die i-te ^   Box hat Höhe h (i), die Breite w (i) und   Tiefe d (i) (alle reellen Zahlen). Du   will einen Stapel von Boxen zu schaffen,   wie möglich ist so groß, aber man kann   Stack nur ein Feld auf einem anderen Feld   wenn die Abmessungen der 2-D-Basis   der untere Kasten jeweils streng größeren   als die Basis 2-D der diejenigen   höhere Box. Natürlich können Sie drehen   eine Box, so dass irgendwelche Nebenfunktionen wie   seine Basis. Es ist auch zulässig zu verwenden   mehrere Instanzen des gleichen Typs von   Box.

Dieses Problem scheint zu kompliziert für mich die Schritte, um herauszufinden. Wie es 3D ist, dass ich drei Folge von Höhe, Breite und Tiefe erhalten. Aber wie es möglich ist, 3 Dimension auszutauschen wird das Problem für mich komplizierter. Also bitte jemand die Schritte erklärt, das Problem zu lösen, wenn es kein Austausch ist, und dann, wie es zu tun ist, wenn Swapping. Ich wurde über das Problem müde. Also bitte, bitte jemand die Lösung einfach Art und Weise erklären.

Answer 1

Ich glaube, Sie können dieses Problem lösen die dynamische Programmierung mit längste aufsteigende Teilfolge Algorithmus: http://people.csail.mit. edu / Bdean / 6,046 / dp /

Answer 2

Der Stapel kann als eine Folge von x betrachtet werden, y, z-Tripletts (x, y ist, um die 2D-Ebene, und Z die Höhe), wobei x (i)> x (i + 1) und y (i) > y (i + 1). Das Ziel ist es, die Summe von z Aufnehmen des Tripletts aus der Menge des verfügbaren Tripletts zu maximieren - jedes Triplett in einer bestimmten Ausrichtung eine Art von Kasten zu sein. Es ist ziemlich leicht zu sehen, dass die Einschränkung x Durchsetzung> y nicht reduziert den Lösungsraum. So dass jede Box 3 Tripletts erzeugt, die jeweils mit w, h, d, wie die Z-Koordinate.

Wenn Sie die Drillinge als gerichtete azyklischen Graphen betrachten, wo Kanten der Länge z exist zwischen zwei Tripletts, wenn die x, y Einschränkungen erfüllen zwischen ihnen, dann ist das Problem des längsten Weg zu finden, durch dieses Graphen.

Answer 3

erster Versuch Lassen Sie sich dieses Problem in 2-D zu lösen:

sagen, Sie haben Rechtecke mit X und Y des, und die Frage ist ähnlich (höchste Turm, aber dieses Mal haben Sie nur Sorge um eine Basisdimension).
so erster, gehen Sie die ganze Sammlung über, jedes Rechteck Duplizieren von 90 Grad (swapping X und Y) zu drehen, mit Ausnahme von Quadraten (wobei X (1) = X (2) && Y (1) = Y (2)) . dies stellt alle möglichen Variationen.
Sie sie dann durch ihre X-Seite sortieren, vom größten bis zum kleinsten. im Fall des doppelten X-Wertes, können Sie den mit dem niedrigeren Y-Wert entfernen.

gleiche Prinzip angewandt in der 3-D-Szenario, nur jetzt Sie nicht nur mehrfach die Größe der Sammlung von 6 (alle möglichen Varianten des W, H, D), sondern von 2. Sie tun dies, indem alle Variationen zu entlassen, wo die Breite geringer ist als die Tiefe (so für jedes i, W (i)> = D (i)), und dann die Variation Abweisung, wobei die Höhe nicht der höchste, noch die niedrigste der drei Dimensionen (weil die anderen beiden Varianten ist, kann geht eine auf den anderen, und dies kann man nicht mitmachen). wieder, auch Vervielfältigungen entlassen (wobei W (1) = W (2) && H (1) = H (2) && D (1) = D (2)).
Dann sollten Sie nach Breite sortiert werden, nur dieses Mal, wenn Sie don t Variationen mit der gleichen Breite wegzuzuwerfen (weil man in einem Turm passen kann, dass eine andere nicht), dann können Sie den LIS-Algorithmus verwenden, wie oben beschrieben @IVlad:

D[1] = h(1);
D[i] = h(i) + max(D[j] | j <= i and we can put tower i on tower j) or simply h(i) if no such D[j] exists.

Der Trick war, wissen Sie, dass die Breite ist die längste der beiden, so dass Sie das erste Element wissen, passt nicht oben auf einem späteren Element.

Answer 4

Ich schlage vor, Sie erstellen einen Baum (oder irgendeine Art von Baumstruktur) und analysiert es mit Tiefensuche, die maximale Höhe der einzelnen vertikalen „Höhe“ Berechnung (depening auf Rotation) Werten.

Das (Ich denke, dies der grundlegende Ansatz ist).

Details über Details:

Die Baumwurzel sollte der Boden, in dem alle Würfel passen auf sein. Von dort erstellen Sie nur die untergeordneten Knoten der möglichen nächsten (Boxen, die in einem bestimmten Dreh ontop der aktuellen Box platziert werden können)-Boxen. Rekursiven tun für jede Box und Rotation.

Wenn der Baum zu bauen ist, durch sie gehen und calc die gesamte Turmhöhe von Boden zu einem Blatt des Baumes.

Answer 5

Eine Lösung für das Problem besteht aus drei Schritten.

1. Sortieren Dimensionen für jede Box, so dass keine zwei Boxen zu vergleichen reduziert ihre entsprechenden Dimensionen zu vergleichen.
2. Sortieren die Reihenfolge der Boxen lexikografisch, so dass für jede Box, die Boxen auf der linken Seite sind die Felder, die passen kann.
3. Tragen Sie der O(n^2) Algorithmus für die Längste Erhöhung Subsequence Problem .

Der dritte Schritt ist die teuerste und Stösse, die Komplexität der Lösung O(n^2). Wenn Sie möchten, eine vollständige Erklärung des Ansatzes lesen, wie jeder Schritt dazu beiträgt, eine Antwort zu finden, und vollständigen Code, einen Blick auf die Blog-Post ich über das Problem geschrieben.