Rucksackproblem mit mehreren Rucksäcken

24/07/2010 - 21:13 von Johannes Bauer | Report spam
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?

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>
 

Lesen sie die antworten

#1 Bastian Erdnuess
24/07/2010 - 23:03 | Warnen spam
Johannes Bauer wrote:

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

Ähnliche fragen