Ich versuche, dieses Problem zu lösen, und ich wollte wissen, ob es bekannte Algorithmen / Lösungen gibt, um das zu lösen.
Problem:
Ich habe n Taschen und n Gegenstände (die entweder gleich oder unterschiedlich schwer sind) in diese Tasche zu füllen. Jeder dieser Taschen hat eine bestimmte Gewichtsgrenze und die n Gegenstände müssen so in diese Taschen gesteckt werden, dass ich den maximalen Platz in jedem dieser Taschen nutzen kann.
Die Taschen sind gleich groß. Will auch wissen, wie man mit Säcken von ungleicher Größe auch löst.
Die meisten Lösungen, die ich gelesen habe, versuchten einen 0/1 Rucksack mit einem Gewicht und einem Wert zu lösen. Sollte ich das Gewicht und den Wert als gleich betrachten? Bin ich auf dem richtigen Weg?
Das ist kein Hausaufgabenproblem.
Dies wird als Problem mit dem Bin-Packing bezeichnet (was NP-schwer ist).
Durch einfaches Sortieren der absteigenden Reihenfolge nach ihren Größen und anschließendes Einfügen jedes Elements in die erste Zelle in der Liste mit ausreichend verbleibendem Speicherplatz erhalten wir 11/9 OPT + 6/9 bins (wobei OPT die Anzahl der im Optimal verwendeten Klassen ist) Lösung). Dies würde leicht O(n²) oder möglicherweise O(n log n) mit einer effizienten Implementierung übernehmen.
Im Hinblick auf optimale Lösungen gibt es keine dynamische Programmierlösung, die so bekannt ist wie für das Rucksackproblem. Diese Ressource hat eine Option - die Grundidee lautet:
%Vor%Der obige Array-Index ist buchstäblich eine Menge. Stellen Sie sich dies als eine Map von set-to-value, einer Bitmap oder eines mehrdimensionalen Arrays vor, wobei jeder Index entweder 1 oder 0 ist, um anzuzeigen, ob wir das Element zu dieser Dimension hinzufügen oder nicht.
Die verknüpfte Ressource berücksichtigt tatsächlich mehrere Typen, die mehrfach vorkommen können - ich habe die obige Lösung daraus abgeleitet.
Die Laufzeit hängt stark von der Anzahl der Gegenstände ab, die in eine Tasche passen - es wird
O(minimumBagsUsed.2maxItemsPerBag)sein.
Im Fall von 1 Tasche ist dies im Wesentlichen das Teilmengen-Summenproblem . Dafür können Sie das Gewicht als Wert betrachten und mit einem Rucksack-Algorithmus lösen, aber das wird nicht wirklich gut für mehrere Taschen funktionieren.
Warum nicht? Betrachte die Elemente 5,5,5,9,9,9 mit einer Beutelgröße von 16 . Wenn Sie nur die Teilmengensumme lösen, verbleiben 5,5,5 in einem Beutel und 9 in jeweils einem Beutel (für insgesamt 4 sacks) und nicht 5,9 in jedem der 3 Beutel. p>
Subset sum / rapsack ist bereits ein schwieriges Problem - wenn es keine optimale Lösung bietet, können Sie auch den obigen sorting / greedy-Ansatz verwenden.
Tags und Links algorithm knapsack-problem