Re: Rucksack-Problem mit Disketten/CD/DVD, Verteilung und Optimierung

On Sun, May 15, 2005 at 02:23:18PM +0200, Raphael H. Becker wrote:
> Die Frage ist allerdings auch, wie "optimal" eine solche Lösung sein
> muss, um trotzdem noch sinnvoll zu sein. Wenn das Ergebnis ist, dass ich
> zB schon aufgrund der Gesamtmenge 45 Rohlinge brauchen werde, dann würde
> es schon gut sein, wenn das ganze letztendlich auf 47 Rohlinge verteilt
> wird, wenn bei händischer (trial-and-error) Sortierung vielleicht 50
> oder mehr rauskommen würden, das mathematisch optimierte Ergebnis 46
> Rohlinge bedeuten würde. Das wäre der Verlust eines Rohlings gegenüber
> der "akademischen" Lösung jedoch ein Gewinn von 3 Rohlingen gegenüber
> der manuellen "Optimierung". Für die Praxis schonmal ein fairer
> Kompromiss.

Du musst ja nicht manuell optimieren. Und fuer den Fall, dass alle Dateien
immer eine Groesse haben, die ein Vielfaches der Blockgroesse darstellen,
kannst du sogar Algorithmen mit linearer Laufzeit finden. Und da bist du mit
der Laufzeit auf _jeden_ Fall deutlich unter der Dauer, die du zum Brennen
einer CD/DVD benoetigst.

Wegen der Anfrage aus der anderen Mail: Buecher darueber gibt es wie Sand am
Mehr. Um nur mal eins rauszupicken, obwohl ich das jetzt sonst nicht so toll
finde, ist eines der vielen Algorithmen-Buecher von Sedgewick. Dieses Buch hat
in diesem Fall den Vorteil, dass es bereits Beispielimplementationen enthaelt,
wenn es auch dafuer auf akademischer Sicht nicht sonderlich in die Tiefe geht,
aber das interessiert dich ja eh nicht so, wenn ich dich richtig verstanden
habe.

> Nebenbei: kann es sein, dass iso9660 Probleme mit Dateien >1GB hat? 
> Die werden bei mir regelmäßig nicht mitgebrannt. Ich splitte die tars
> dann auf mehrere kleinere Teile und brenne mehrere Dateien pro DVD.

Das Dateisystem kann keine linearen Streams speichern, die groesser als 1GB
sind. Dies ist aber kein Problem, da eine Datei auch aus mehreren linearen
Streams bestehen koennen. Aeltere Versionen von mkisofs konnten damit aber
nicht umgehen konnten. Du solltest also erst mal versuchen, mkisofs zu
updaten, wenn du da noch eine alte Version hast. Es koennte natuerlich auch
sein, dass das eine oder andere Betriebssystem beim Lesen noch schwierigkeiten
haben. Du kannst ja mal testen, ob du die gebrannte DVD auf einem aktuellen
Linux-System korrekt lesen kannst. Von Linux weiss ich naemlich, dass es dort
auf jeden Fall funktioniert.

Robert

-- 
Robert Schiele			Tel.: +49-621-181-2214
Dipl.-Wirtsch.informatiker	mailto:rschiele@uni-mannheim.de