Verpackung unterschiedlich große Datenmengen in mehrere Behälter

Question

EDIT: Es scheint, wie dieses Problem "Cutting Lager Problem" genannt wird,

Ich brauche einen Algorithmus, der mir die (raum-) optimale Anordnung der Stücke in Behältern gibt. Eine Möglichkeit wäre die größeren Brocken in dem ersten Stelle setzen werden. Aber sehen Sie, wie dieser Algorithmus in diesem Beispiel nicht:

Chunks        Bins
-----------------------------
AAA BBB CC DD (       ) (   )

Algorithm     Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal       (AAACCDD) (BBB)

"Größte zuerst" kann nicht in DD passen. Vielleicht hilft es, eine Tabelle wie folgt zu erstellen:

Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB

Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB

Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD

Answer 1

Dies ist im Grunde eine Variante des bin-Verpackung Problems. Dieses Problem ist bekannt NP-schwer, sein also nicht erwarten, einen effizienten Algorithmus optimal für komplexe Fälle zu finden (das heißt mit vielen Objekten und Bins).

Wenn jedoch die Anzahl der Objekte / Behälter relativ klein ist, werden Sie wahrscheinlich in Ordnung sein nur erschöpfend alle möglichen Kombinationen mit einem Tiefensuche .

Das ist ziemlich einfach zu implementieren: Nehmen Sie nur das erste Objekt, dann rekursiv erneut ausführen, den Algorithmus mit dem ersten Objekt in jedem des Behälter wiederum platziert (das heißt Subtrahieren die Größe des Objekts aus dem verfügbaren ist Raum). Schließlich müssen Sie nur den Überblick über die beste „Lösung“ halten gefunden, so weit und geben diese als Ihre endgültige Antwort, wenn Sie alle Kombinationen ausprobiert haben.

Sie können auch in der Lage machen diesen Algorithmus Algorithmus laufen schneller durch:

• Unter Berücksichtigung aller Objekte gleicher Größe als gleichwertig
• Pruning den Suchbaum (das heißt verfrühte Rückkehr von einem Zweig), wenn Sie können möglicherweise nicht die aktuelle beste Lösung schlagen z.B. wenn Sie bereits eine perfekte Passform
gefunden

aktualisiert basierend auf Kommentare zu Problemgröße

Da es sieht aus wie Sie eine sehr große Anzahl von Chunks haben zu behandeln, möchten Sie vielleicht die folgende versuchen:

• Setzen Sie die größten 10-20 Stücke unter Verwendung einer erschöpfenden Suche wie oben
• Weisen Sie den Rest einen größten fit Ansatz mit

Answer 2

Mikera hat Recht: diese mehr Knapsack Problem (eine Variante des Bin-Packing-Problems) ist NP hart .

Hier sind ein paar Optionen (kopiert von meiner Antwort auf eine ähnliche Frage):

• Brute-Force, oder besser noch, Zweig und gebunden. Nicht Skala (überhaupt!), Aber werden Ihnen die optimale Lösung (wahrscheinlich nicht in unserem Leben, obwohl) finden.

• deterministische Algorithmus: Sortieren der Stücke auf dem größten Größe und gehen Sie durch diese Liste eins nach dem anderen, und weisen Sie die besten verbleibenden Stelle. Das wird sehr schnell fertig, aber die Lösung kann weit sein von einem optimalen (oder möglich). Hier ist ein schönes Bild ein Beispiel zeigt, was schief gehen kann. Aber wenn Sie wollen halten sie es einfach, das ist der Weg zu gehen.

• Meta-Heuristik, aus dem Ergebnis eines deterministischen Algorithmus zu starten. Dies wird Ihnen ein sehr gutes Ergebnis in angemessener Zeit, besser als das, was Menschen kommen mit. Je nachdem, wie viel Zeit Sie es geben und die Schwierigkeit des Problems es möglicherweise oder möglicherweise nicht die optimale Lösung sein. Es gibt ein paar Bibliotheken gibt, wie zum Beispiel geifert Planner (Open-Source-Java).

Answer 3

Ein allgemeiner bester Algorithmus für dieses Problem existiert noch nicht ( Bin Packing Problem ) . Sie können ein paar verschiedenen Ansätze auf wikipedia finden und / oder für das „Ist Packing Problem“ googeln und vielleicht „Knapsackproblems“ würde auch etwas Hilfe bieten.

Answer 4

Donald Knuth Tanzen Verbindungen Algorithmus ist schnell zu Lösungen zu finden Probleme „exakt abdeckt“.