On Sat, May 14, 2005 at 03:31:07PM +0200, Raphael H. Becker wrote:
> Hallo zusammen,
>
> ich suche eine universelle Lösung für ein "einfaches Problem":
>
> Ich habe eine Tabelle mit Größen und Objekten, zB Dateien oder
> Verzeichnisse in bspw folgendem Format:
>
> 230|bla.tgz
> 1023|foo.rar
> 876|fasel.zip
> 543|bar.mp3
> ...
>
> und möchte diese Liste anhand einer gegebenen Kapazität pro Einheit (zB
> 716800 = 700MB) möglichst effizient verteilen, wobei die Reihenfolge
> dabei egal ist.
>
> Die Ausgabe soll dann zB als Liste in mehrere Dateien oder in der Form
> aussehen (zB für Diskette 1440):
>
> 290|bla.tgz|1
> 583|bar.mp3|3
> 889|fasel.zip|1
> 1123|foo.rar|2
> ...
>
> Dabei sind folgende Optimierungsschritte denkbar:
>
> [...]
Die angesprochenen Techniken haben alle den Fehler, dass sie auf einem
Greedy-Algorithmus basieren, was aber beweissbar allgemein nicht zu einer
optimalen Loesung fuer das 0-1-Rucksackproblem fuehren kann.
Eine effiziente Ermittlung einer optimalen Loesung ist zum Beispiel durch
dynamische Programmierung moeglich, wie du das im Rahmen deines TI-Studiums in
der Algorithmen-Vorlesung gelernt hast. Solltest du dich nicht mehr erinnern
und keine Unterlagen mehr haben, findest du Informationen zu dynamischer
Programmierung auch in jedem guten Einfuehrungsbuch fuer Algorithmen.
Robert
--
Robert Schiele Tel.: +49-621-181-2214
Dipl.-Wirtsch.informatiker mailto:rschiele@uni-mannheim.de
- application/pgp-signature Anhang: stored
Received on Sat May 14 17:06:41 2005