(23.10.2021, 16:12)andreas42 schrieb: mir fiele spontan ein, immer den längsten Titel hinzuzufügen, der noch in den verbleibenden Platz passt. Aber damit übersieht man Kombinationen, wo weniger Restzeit übrig bleibt.
Ich hatte eben exakt den gleichen Gedankengang. Wenn man mal (einfach konstruierter Fall) von 10 MB freiem Platz ausgeht, und man hat folgende Dateien:
5 MB
4 MB
2 MB
2 MB
2 MB
... und dann würde man nach dem "Immer die größte Datei, die noch passt"-Prinzip vorgehen, dann würde man die Dateien von 5 und 4 MB nehmen, und am Ende wäre noch 1 MB freier Platz übrig. Mit 4 MB und drei mal 2 MB würde man den Platz dagegen optimal nutzen. Aber wie kann man das herausfinden, ohne alle Kombinationen rechenzeitintensiv durchzuprobieren? Gibt's dafür einen Algorithmus?
Das müsste man mal tiefgehend drüber nachdenken.
Edit: Zweiter Anlauf. Das Ziel war ja nicht, einen einzelnen Datenträger mit den vorhandenen Daten optimal auszufüllen (was ich oben getan habe), sondern die Gesamtmenge der Daten auf möglichst wenige Datenträger (mit möglichst wenig freiem Platz) zu verteilen. Und dann könnte es doch sein, daß die Methode "Immer die größte Datei, die noch passt" zum optimalen Ergebnis führt.
Ein möglicherweise störender Effekt wäre allerdings, daß die großen Dateien tendenziell auf den ersten CDs landen würden, während der letzte viele kleine Dateien enthielt. Bei Musikstücken könnte dann zum Schluss ein reiner Punk-Sampler herauskommen.
