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

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:

Gesamtgröße (GS): 2885
min. Anzahl-Datenträger (AD_min): 3

Optimierung 0:
In gegebener Reihenfolge verteilen

290|bla.tgz|1
583|bar.mp3|1
889|fasel.zip|2
1123|foo.rar|3

Ok, für diese Liste wird man nie über 3 Disketten kommen. Hier reicht
Optimierung 0.

Hat nun eine Datei 10kb weniger, dann sieht das schon ganz anders aus:

GS wäre dann 2875 kb, also 2 Disketten:

290|bla.tgz|1
583|bar.mp3|1
889|fasel.zip|2
1113|foo.rar|3

Hier würden auch 3 Disketten herauskommen, egal welche Optimierung man
verwendet. Aber nach welchem Algorithmus durchsucht man die Liste nach
etwaig günstigeren Lösungen?

zB wie packe ich ein distfiles-Verzeichnis kostengünstig auf CD-R mit
700MB/Medium?  Siehe zB http://rabe.uugrn.org/temp/distfiles_sizes.txt

Insgesamt sind es 1843662 kB, was rechnerisch 2.5 also 3 CDs gibt,
selbst mit 650MB/Medium noch.

Eine Optimierung wäre, die Dateien absteigend nach Größe zu sortieren,
d.h. größte zuerst und dann solange reihum auf die vorhandenen
Kapazitäten verteilen, bis alles verteilt ist.

Das ist recht effizient, wenn die Dateien durchnittlich viel kleiner sind 
als ein Medium.

Wie funktioniert das, wenn die Dateien/Verzeichnisse durchschnittlich
mehr als halb so gross sind, wie ein Medium?

Das Optimierungsziel ist es, möglichst nicht mehr als die unbedingt
benötigten Datenträger zu verwenden, was im Grenzfall recht schwirig
wird. 

Wie kann man den Algorithmus noch weiter optimieren?

Beispiel: 3 CDs werden gebraucht aufgrund der Gesamtkapazität, 
zB 3*650MB = 1996800kb. Sei eine Liste, deren Gesamtgröße 1991608 (also
5MB weniger als die Gesamtkapazität) ist und deren kleinste Datei > 5MB
ist. Mit Glück würde man durch sortieren die 3 CDs gerade so
vollbekommen, zB mit jeweils freien Kapazitäten von 1,2 und 3MB. 

Nur wie ermittelt man die Verteilung, daß es auch sicher passt?
Vorausgesetzt man kann die Liste durch Vertrauschen von Elementen genau
so einpassen. 

Aber dazu müsste man (brute force) alle Kombinationen durchtesten. 
Das ist sicher keine Lösung. Wie gehts schöner?

Mein Ansatz wäre folgender:

Versuch 1:
a) Dateien in gegebener Reihenfolge auf die Medien verteilen
b) Prüfen, ob rechnerisch mindestens ein Medium dabei eingespart werden
   könnte --> Versuch 2

Versuch 2:
a) Verteilen aller Dateien auf die 3 CDs in absteigender Reihenfolge 
   nach Größe sortiert. 
b) Prüfen, ob rechnerisch mindestens ein Medium dabei eingespart werden
   könnte --> Versuch 3


Versuch 3:
a) Die Sortierte Liste aus Versuch 2 verwenden
   Auf den Medien nach ähnlich großen (Differenz maximal die freie
   Restkapazität eines Mediums) Dateien suchen, die sofern es passt 
   tauschen, wenn dabei die Restkapazität eines der beiden Medien 
   verkleinert würde. Dabei die Restkapazität beider Medien möglichst
   geschickt auf ein Medium verschieben.  

b) Prüfen, ob die größte Datei vom letzten Medium in die eben vergrößerte
   Restkapazität reinpasst, falls ja, dann verschieben

c) Wenn noch eine Datei auf dem letzten Medium liegt, Schritte a) und b) 
   wiederholen

Mir fällt es schwer, eine Abbruchbedingung zu finden für den Fall "geht
einfach nicht", er würde sonst ewig rumprobieren.  Schritt 3a finde ich 
"gefährlich" hinsichtlich möglicher Laufzeiten, gerade wenn es zB 30, 40
oder 100 Medien sind.

Es wäre zwischen Schritt 2 und 3 durchaus denkbar, mehr als ein Medium 
einzusparen, wenn nach Versuch 2 die Gesamt-Restmenge größer ist, als ein 
Medium. Auch hier gibt es triviale Situationen, wo man auf den ersten
Blick erkennt, dass eine weitere Optimierung sinnlos ist, zB wenn man
nur Dateien hat, die  jeweils größer als ein halbes Medium sind.

Hier suche ich noch nach einer intelligenten Lösung bzw nach der Möglichkeit, 
eine mögliche Lösung (kostengünstig) vorab als existent zu beweisen, damit es 
sich überhaupt lohnt, weiter (kostenintensiv) zu optimieren. 

Eine solche Vorhersage könnte zB mit Hilfe von etwas Statistik ("Magie")
ausrechnen, auf wieviele Medien man überhaupt runteroptimieren kann,
d.h. das Ziel definieren, auf das man hinoptimieren kann um sinnloses
optimieren auf nichterfüllbare Ziele zu vermeiden (Laufzeitoptimierung).

Falls es nicht ohnehin ein viel schoeneres Optimierungsverfahren gibt :)

So einfach scheint das alles nicht zu sein.

MfG
-- 
Raphael Becker                                    http://rabe.uugrn.org/
                      http://schnitzelmitkartoffelsalat.und.rahmspin.at/
.........|.........|.........|.........|.........|.........|.........|..