Rucksackproblem mit mehreren Rucksäcken
Johannes Bauer
bin gerade am Grüblen, ob es für eine Variante des Knapsack-Problems
einen eigenen Namen finde:
n Gegenstände mit Gewichten w_i sollen auf Rucksäcke der Kapazität k
aufgeteilt werden. Dabei ist sum(w_i) > k, d.h. ein Rucksack nicht
ausreichend. Die Anzahl der Rucksäcke ist unendlich, deren benötigte
Anzahl soll minimiert werden (untere Schranke ist hier also
ceil(sum(w_i) / k)).
Gibt es dafür einen Namen? Ich finde gerade nichts gescheites, versuche
es aber womöglich nur mit den falschen Begriffen. Gibt es einen
Lösungsalgorithmus, der effizient berechenbar ist?
Viele Grüße,
Johannes
--
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1...@speranza.aioe.org>
Bastian Erdnuess
> Hallo zusammen,
>
> bin gerade am Grüblen, ob es für eine Variante des Knapsack-Problems
> einen eigenen Namen finde:
>
> n Gegenstände mit Gewichten w_i sollen auf Rucksäcke der Kapazität k
> aufgeteilt werden. Dabei ist sum(w_i) > k, d.h. ein Rucksack nicht
> ausreichend. Die Anzahl der Rucksäcke ist unendlich, deren benötigte
> Anzahl soll minimiert werden (untere Schranke ist hier also
> ceil(sum(w_i) / k)).
>
> Gibt es dafür einen Namen? Ich finde gerade nichts gescheites, versuche
> es aber womöglich nur mit den falschen Begriffen. Gibt es einen
> Lösungsalgorithmus, der effizient berechenbar ist?
Ich hab von dem Problem schonmal in der Form gehört, dass n Pakete mit
Gewichten w_i auf so wenige LKW (trucks) wie möglich mit Kapazität je k
aufgeteilt werden sollen.
Ich kann mich gerade nicht mehr daran erinnern, welchen Namen das
Problem hatte, oder in welchem Zusammenhang (Greedy, D&C, Dynamic,
Netzwerke, NP, ...) ich davon gehört hab.
Aber vielleicht gibt obige Formulierung Hilfe dabei, nach welchen Namen
(z. B. trucking problem, oder so) gesucht werden muss.
Gruß,
Bastian
Karl Heinz
> Aber vielleicht gibt obige Formulierung Hilfe dabei, nach welchen Namen
> (z. B. trucking problem, oder so) gesucht werden muss.
Ich hab einfach mal multiple knapsack problem eingegoogelt, Treffer, z.B.