Hi Kevin,

Kevin Fleischer schrieb:
> In einem Forum in dem ich öfters unterwegs bin kam die Frage auf, wie man die beste auslastung von DVDs berechnen kann.
> Und zwar hat der betreffende eine Menge Ordner unterschiedlicher größe und möchte die auf möglichst wenige DVDs brennen. Wie kann man das bestimmen?

Der "offizielle" Name dafür dürfte "BinPacking" sein. Nun ist die Frage,
ob die Menge der Dateien endgültig ist oder ob im Laufe der Zeit immer
neue Dateien hinzukommen. In letzterem Fall wäre es dann ein
"Online-Problem".
So richtig kenne ich mich nicht aus. Was mir einfällt ist folgendes.
Zunächst einmal für die Offline-Variante (man weiß, daß nichts mehr
dazukommt):
Das kann man sehr effizient approximieren. Die Objekte (Dateien) der
Größe nach absteigend sortieren. Dann vorne anfangen und das Objekt in
den ersten Behälter (DVD) packen, wo es reingeht. Dann das zweitgrößte
Objekt, usw. Solange wiederholen, bis alle Objekte verteilt sind. Damit
erhält man eine Güte von 2. Das heißt man benötigt maximal doppelt so
viele DVD's wie nötig wären. Das ist "in echt" natürlich ein ziemlicher
Verschnitt, dafür geht es schnell.
Will man die optimale Lösung, dann muß man zu den langsamen Algorithmen
greifen. Außer Brute-Force fällt mir da nicht viel ein. Es gibt sicher
auch Ansätze mit dynamischer Programmierung. Das ist dann zwar auch noch
exponentiell aber besser
Möglicherweise funktioniert Branch-and-Bound auch gut. Müßte man mal
ausprobieren. Schranken fallen mir zwar ein, aber es ist mir zu
kompliziert zu schreiben Ich denke, Du findest im Netz einiges dazu.

So, jetzt ein paar Gedanken zur Online-Variante.
Wenn immer wieder neue Objekte hinzukommen, kann man aus einer
Momentaufnahme natürlich keine optimale (Global-)Lösung konstruieren.

Ich habe sowas vor einiger Zeit mal realisiert (ob ich dabei gute Ideen
hatte, sei dahingestellt )
Zuerst das Ergebnis, wenn Du damit unzufrieden bist, mußt Du nicht
weiterlesen
Meine Objekte waren zwischen 500MB und 1,8 GB groß. Wenn ich >=11
Objekte zur Verfügung standen, füllte der Alg. mindestens eine DVD so,
daß maximal 10 MB frei blieben (oft < 1MB). Also ein Verschnitt im
Promille-Bereich.
Ich habe mir keine Mühe beim Optimieren gegeben (und Java benutzt ),
daher war bei >20 Objekten meist Schluß, jedenfalls hat es dann schon
Minuten gedauert und so lange wollte ich nicht warten.
Also hab ich immer nur 18-19 Objekte zur Verfügung gestellt und der Alg.
hat mir zwei bis drei DVD's "praktisch randvoll" gepackt und dann habe
ich die nächsten Objekte nachgeschoben. Im Rückblick bin ich sehr
zufrieden, die 10MB Grenze hielt die ganze Zeit stand.

Nun die Idee:

Zuerst habe ich die Anzahl der nötigen DVDs trivial nach oben
beschränkt: Wenn die k größten Objekte auf eine DVD passen, brauche ich
maximal #Objekte/k DVDs. Je kleiner diese Schranke, um so schneller geht
der Algorithmus. Aber man darf nicht zu genau werden, sonst kriegt man
viele DVDs relativ voll. Da Online-Variante, ist mir aber wichtiger,
einige DVDs ganz voll zu machen. Die anderen will ich ja mit Objekten
der Zukunft füllen.

Angenommen, wir haben n Objekte und m Behälter zur Verfügung. Nun will
ich ja eine Lösung, wo vor allem die ersten Behälter möglichst voll sind.
Angenommen, wir haben eine zulässige Verteilung V der Objekte. Dann
bewerte ich V durch f(V)=\sum_{i=1}^m i*#(freie Bytes in Behälter i).
Und nun suche ich die Verteilung V' mit maximalem f. Dadurch wird vorne
möglichst dicht gepackt und die hinteren Behälter bleiben eher leer.
Will man diesen Effekt verstärken, kann man aus i auch i^2 machen. Zum
Abschwächen irgendetwas <<i nehmen (log i, \sqrt i oder so).

Nun suche ich also per Backtracking nach V'. Da das sehr lange dauert,
führe ich noch S(V) mit, eine obere Schranke an f. Dazu berechne ich S,
sobald ich ein weiteres Objekt verteilt habe. S arbeitet also auf
partiellen Verteilungen. Es nimmt an, daß die Restobjekte optimal auf
die ersten Behälter verteilt werden können (so als wären sie flüssig)
und berechnet dann f von der fiktiven Verteilung. Dadurch kann ich eher
abbrechen, wenn ich bereits in einem anderen Ast eine bessere Verteilung
gefunden habe. Diese Schranke kann man noch verfeinern, aber es ist mir
wieder zuviel Schreibaufwand
Das ganze funktioniert also ein bißchen wir Branch-and-Bound, bloß ohne
"Branch"
Das Branchen würde sich aber lohnen, denke ich, obwohl es sehr zu Lasten
des Speichers gehen würde.

Für weiter Details oder "Philosophien" kommste bitte in mein Büro,
E-Mail schreiben dauert länger als reden.

Ich hoffe, einen kleinen Einblick gegeben zu haben. Zumindest hast Du
die wesentlichen Begriffe, um im Netz weiterzugucken.

Viele Grüße
Andre'