Re: OT: Optimalen Inhalt einer CDR bestimmen
Am Sat, 18 Mar 2006 15:12:50 +0100 schrieb Moritz Lenz:
> Das Problem nennt sich, mich mein eines Informatiksemester nicht im Stich
> lässt ;), "eindimensionales Rucksackprobem".
Knapp daneben. Es ist, um genau zu sein, das "Bin Packing"-Problem, bei
dem es darum geht, die Anzahl der zu füllenden Behälter (hier:
CD-Rohlinge) zu minimieren, aber auf jeden Fall alle Items (Verzeichnisse)
"einzupacken". Im Gegensatz dazu soll beim Rucksackproblem das zur
Verfügung stehende Volumen *eines* Behälters (des Rucksacks) durch
geschickte Auswahl der verschieden großen Items möglichst stark gefüllt
werden werden. Zugegebenermaßen sind die Probleme ähnlicher Natur (es
sind beide "Packing Probleme" und beide NP-vollständig), aber sie
erfordern unterschiedliche Algorithmen.
Siehe auch:
http://de.wikipedia.org/wiki/BIN_PACKING
http://de.wikipedia.org/wiki/Rucksackproblem
Gruß
Adalbert
Reply to: