Dies ist bekannt als the bin packing problem (die NP-hart ist).
Durch einfaches Sortieren der absteigenden Reihenfolge nach ihren Größen und dann Einfügen jedes Elements in den ersten Behälter in der Liste mit ausreichend verbleibendem Speicherplatz, erhalten wir 11/9 OPT + 6/9 Bins (wobei OPT die Anzahl der in der optimalen Lösung verwendeten Bins ist). Dies würde leicht O(n²) oder möglicherweise O(n log n) mit einer effizienten Implementierung übernehmen.
In Bezug auf optimale Lösungen gibt es keine dynamische Programmierlösung, die so bekannt ist wie für das Rucksackproblem. This resource hat eine Möglichkeit - die Grundidee ist:
D[{set}] = the minimum number of bags using each of the items in {set}
Then:
D[{set1}] = the minimum of all D[{set1} - {set2}] where set2 fits into 1 bag
and is a subset of set1
Der Arrayindex oben ist buchstäblich ein Satz - man denke an das als eine Karte von Einstellung auf einen Wert, eine Bitmap oder ein mehrdimensionales Array, wobei jeder Index ist entweder 1 oder 0, um anzugeben, ob wir den dieser Dimension entsprechenden Artikel einschließen oder nicht.
Die verknüpfte Ressource berücksichtigt tatsächlich mehrere Typen, die mehrmals vorkommen können - ich leitete die obige Lösung daraus ab.
Die Laufzeit wird stark von der Anzahl der Artikel abhängen, die in eine Tasche passen - es wird O(minimumBagsUsed.2maxItemsPerBag) sein.
Im Fall von 1 Beutel ist dies im Wesentlichen the subset sum problem. 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 Artikel 5,5,5,9,9,9 mit einer Beutelgröße von 16. Wenn Sie nur Teilmenge Summe lösen, sind Sie mit 5,5,5 in einem Beutel und 9 in einem Beutel (für insgesamt 4 Beutel), anstatt 5,9 in jedem der 3 Beutel.
Subset sum/rapsack ist bereits ein schwieriges Problem - wenn es keine optimale Lösung bietet, können Sie auch den Sortier/Greedy-Ansatz verwenden.
Sind die Taschen gleich groß? – JensG
Ja, die Taschen sind gleich groß. Will auch wissen, wie man mit Taschen von ungleicher Größe auch löst. – Jony
Sollte das nicht gleichbedeutend mit dem Problem sein, den Beutel 'N' mit dem Rest der nach dem Befüllen der Beutel' 1' bis 'N-1' übriggebliebenen Ware zu füllen? Ungleiche Größen sind (wahrscheinlich) schwieriger. – JensG