Suche: Algo um Platz optimal zu füllen

Dirk Schwarzmann

unread,

9 Jul 2002, 07:54:1209/07/2002

to

Hallo,

ich suche einen Algorithmus, mit dem ich einen vorgegebenen Platz
(in diesem Fall ein-dimensional) optimal mit ebenfalls vorgegebenen,
natürlich nicht gleich großen Teilen ausfüllen kann.
Hm, vielleicht doch ein wenig zu abstrakt, also erklär ich mal mein
Problem:

Ich möchte mir eine kleine Anwendung schreiben, die mir für eine Liste
von Dateien ausgibt, in welcher Kombination ich sie am besten auf
mehrere Datenträger (deren Größe bekannt ist) verteile, um deren
Kapazität optimal zu nutzen.
Sicher ist so ein Algorithmus schon lange bekannt, ich kenne aber
seinen Namen nicht :-(
Ich brauche, wie das Beispiel deutlich macht, nur eine ganz einfache
eindimensionale Variante, kann mir einer helfen?

Vielen Dank im voraus,
Dirk
--
http://www.dirk-schwarzmann.de/
"Wenn man nur einen Hammer hat, sieht plötzlich jedes Problem wie ein
Nagel aus." (Matthias Esken in de.comm.infosystems.www.authoring.misc)

Lutz Donnerhacke

unread,

9 Jul 2002, 08:19:2309/07/2002

to

* Dirk Schwarzmann wrote:
>ich suche einen Algorithmus, mit dem ich einen vorgegebenen Platz
>(in diesem Fall ein-dimensional) optimal mit ebenfalls vorgegebenen,
>natürlich nicht gleich großen Teilen ausfüllen kann.

Das ist das Rucksackproblem.

>Ich möchte mir eine kleine Anwendung schreiben, die mir für eine Liste
>von Dateien ausgibt, in welcher Kombination ich sie am besten auf
>mehrere Datenträger (deren Größe bekannt ist) verteile, um deren
>Kapazität optimal zu nutzen.

Die optimale Lösung des Rucksackproblems ist NP hart, d.h. Du wirst
expotentiellen Aufwand (über Deine Fileanzahl) treiben müssen. bei 10
Dateien, hast Du in der Größenordnung von 1024 Rechenschritten zu testen.
Bei 100 Dateien, sind es 1 267 650 600 228 229 401 496 703 205 376 Rechen-
schritte. Du wirst also im Bereich der heuristischen oder generischen
Algorithmen suchen müssen, um ein schnelles, aber eben nur fast immer
optimales Ergebnis zu bekommen.

Vorschlag: Verteile die Dateien von groß nach klein auf.

Martin Fuchs

unread,

9 Jul 2002, 08:05:5409/07/2002

to

> Ich möchte mir eine kleine Anwendung schreiben, die mir für eine
Liste
> von Dateien ausgibt, in welcher Kombination ich sie am besten auf
> mehrere Datenträger (deren Größe bekannt ist) verteile, um deren
> Kapazität optimal zu nutzen.
> Sicher ist so ein Algorithmus schon lange bekannt, ich kenne aber
> seinen Namen nicht :-(

Klingt nach einem modifizierten "Rucksack"-Problem.

Das Rucksack-Problem ist allerdings NP-vollständig, also für grosse
Datenmengen praktisch nicht berechenbar.

Es gibt allerdings _genügend_ Algorithmen, die zwar nicht optimale,
aber ganz vernünftige Lösungen liefern.

goggle mal nach:

- Greedy - Algorithmen
- Rucksack-Problem

mf

Pascal Lippmann

unread,

10 Jul 2002, 04:52:3810/07/2002

to

Martin Fuchs schrieb in Nachricht ...

>> Ich möchte mir eine kleine Anwendung schreiben, die mir für eine Liste
>> von Dateien ausgibt, in welcher Kombination ich sie am besten auf
>> mehrere Datenträger (deren Größe bekannt ist) verteile, um deren
>> Kapazität optimal zu nutzen.

>Klingt nach einem modifizierten "Rucksack"-Problem.

Ich kenne diesen Spezialfall des "Rucksack"-Problems unter dem Namen "Bin
Packing". Sehr einfache Heuristiken sind z.B. "first fit" oder "best fit".

Mfg Pascal

Dirk Schwarzmann

unread,

10 Jul 2002, 10:25:5510/07/2002

to

Besten Dank, bin packing scheint mein Problem am besten zu addressieren.
Auch das Ruck/Knapsack-Problem bietet einen Ansatz, man muß dabei
allerdings den Gewinn anders definieren.

> >Klingt nach einem modifizierten "Rucksack"-Problem.
>
> Ich kenne diesen Spezialfall des "Rucksack"-Problems unter dem Namen "Bin
> Packing". Sehr einfache Heuristiken sind z.B. "first fit" oder "best fit".

Vielen Dank für Eure Antworten,