Es gibt eine Diskussion mit ähnlichem Namen unter . Diese wurde allerdings schon geschlossen, da sie schon etwas älter ist.

Das Problem, das ich habe ist sehr ähnlich. Ich habe auch einen Stapel unterschiedlich großer Dateien, es kommen aber nach und nach welche dazu. D. h. es ist nicht erforderlich alle Dateien sofort auf DVDs zu verteilen, sondern es ist gewünscht so viele auf DVDs zu verteilen, dass die DVDs möglichst gut ausgenutzt sind und die restlichen Dateien zu lagern, bis genug weitere Dateien vorhanden sind um erneut verteilen zu können. Der unter der alten Diskussion genannte Algorithmus ist also hier nicht zielführend. Bei diesem war die Idee immer die größten Dateien zu nehmen und dann immer kleinere bis die DVD voll ist. Hier ist ein Beispiel, bei dem das nicht funktionieren wird:

Zur besseren Übersichtlichkeit gehen wir davon aus, dass die DVD 10 GB Platz hätte. Die Dateien haben folgende Größe:

9,0
8,2
4,7
4,7
0,6
1,0

Nach genanntem Algorithmus würden die Dateien wie folgt verteilt werden:

DVD1: 9,0 und 1,0 freier Speicherplatz 0
DVD2: 8,2 und 0,6 freier Speicherplatz 1,2
DVD3: 4,7 und 4,7 freier Speicherplatz 0,6

Ich bin aber auf der Suche nach einem Algorithmus der folgende Verteilung durchführen würde:
DVD1: 9,0 und 1,0 freier Speicherplatz 0
DVD2: 4,7 und 4,7 und 0,6 freier Speicherplatz 0
Und die Datei mit der Größe 8,2 aufhebt bis zum nächsten Durchlauf.

Die DVD-Programme, die ich kenne, welche eine automatische Verteilung durchführen machen das immer sehr platzverschwenderisch und natürlich nicht mit dem genannten Rest.

Hat jemand eine Idee, wie man den Algorithmus aufbauen kann? Es kann sich natürlich bei der Anzahl der Dateien um beliebig viele handeln und der freie Speicherplatz muss nicht unbedingt 0 sein, aber eben möglichst klein.

Weil es bei den heutigen Preisen von Rohlingen kaum lohnt sich darüber auch nur Gedanken zu machen?
Das wirst Du um Handarbeit nicht herum kommen. Wie wäre es mit Images in der Größe einer DVD und Du kopierst die Dateien rein, bis das Image voll ist?

Toast kann Dateien und Ordner splitten. Auf den DVDs liegt dann ein kleines Programm, dass die Dateien auf dem Zielcomputer zusammenfügt.

Ich möchte die Dateien nicht splitten, sondern sie sollen unkomprimiert auf die DVD kopiert werden, damit sie von dort sofort wieder gelesen werden können.

Dass ich dafür etwas programmieren muss ist mir klar. Mir fehlt wie gesagt nur die Idee für den Algorithmus, der das bewerkstelligt. Die Programmierung mit Applescript wäre dann eine Kleinigkeit.

@jogoto: Was für einen Vorteil das Image bringen soll erschließt sich mir nicht. Wenn ich einfach Dateien wie sie kommen hinein kopiere ist das Problem der Verteilung (siehe mein Beispiel) noch nicht gelöst.

Vielen Dank aber für die Tipps.

Einem Image kann man eine feste Größe zuweisen. Wenn Du mehrere Images wie Ordner verwendest, sagt Dir der Finder, wenn das DVD-Image voll ist und Du kannst es brennen und das nächste verwenden.
Für die bereits vorhandenen Daten ist es erst mal Handarbeit aber sicher auch nicht mehr als jetzt was zu programmieren. Für die kommenden Daten ist es einfach nur eine Umstellung (Images statt Ordner).

Ich würde die pure Rechenleistung ausnutzen und die Größen der zu sichernden Dateien solange zusammenwürfeln, bis sich der Füllungsgrad einer DVD nicht mehr weiter verbessert.

Und ich würde brennen sobald die neueste Datei die Mac DVD Größe überschreitet. Andernfalls kann es vorkommen das man auf lange Zeit keine(n) "passenden Partner" findet und daher Dateien nie ihren Weg auf DVD finden.
Im Normalgebrauch dürften die Kosten für die DVDs unter den Tisch fallen. Andernfalls ist es ein einzuplanender und gegebener Kostenanteil oder das falsche Medium.
Vielleicht solltest du mal den Hintergrund deiner Aufgabe posten

Der Hintergrund der Aufgabe ist, dass ich ein DVD-Archiv habe, in das nur eine begrenzte Anzahl DVDs hineinpasst. So eines, dass sich dreht und die DVDs automatisch auswerfen kann. Auch wenn die DVDs an sich super billig sind ist es das Gerät nicht und dahinein passen nur 150 DVDs und es benötigt ziemlich viel Platz. Daher versuche ich den Platzbedarf für die Filme, die ich vom Fernsehen aufnehme so gut wie möglich zu reduzieren. Bevor jetzt jmd. schreibt, ich solle die Filme doch auf einer Festplatte speichern, kann ich nur sagen, dass ich das zusätzlich auch noch mache. Es dient nur einem Backup und der Möglichkeit ohne lange zu suchen jmd. einen bestimmten Filme schnell ausleihen zu können. Das aber nur zum Hintergrund.

Okay, wir ändern die Aufgabenstellung mal geringfügig ab. Wir beschränken uns mal bei der Betrachtung auf eine DVD und beliebig viele Dateien. Ziel ist es diese eine DVD mit einer Auswahl der Dateien so zu füllen, dass der übrige freie Speicherplatz möglichst gering wird. Am besten natürlich = 0. Das häufig erwähnte Image bringt mir hier leider nichts, da mein Script die Größe der Dateien ermitteln kann und auch weiß wie viel Platz es auf einer DVD hat. Es soll eigentlich nur die geeigneten Dateien markieren, so dass ich sie auf mein Brennprogramm rüberziehen kann. Mehr nicht. Als Algorithmus habe ich mir mittlerweile folgendes ausgedacht:

Beispiel-Dateigrößen: 8, 1, 4, 6
Beispiel-DVD-Kapazität: 10


1. Dateien der Größe nach sortieren (8, 6, 4, 1)
2. DVD von der größten Datei beginnend füllen, bis keine Datei mehr darauf passt (8, 1)
3. Beenden, wenn der restliche Speicherplatz gleich 0 ist (Speicherplatz = 1)
4. Verteilung und Speicherplatzgrösse merken

5. Grösse der grössten Datei auf der DVD plus restlicher Speicherplatz geteilt durch 2 ermitteln (4,5)
6. Prüfen ob es eine Datei gibt, deren Speicherplatz <= dieser Grösse ist (ja: 4)
7. Ersetzen der größten Datei durch diese (4,1)
8. Restlichen Speicherplatz ermitteln (5)
9. Prüfen ob es eine Datei gibt, die kleiner gleich dieser Grösse ist (gibt es nicht)
10. Wenn ja, diese Datei aufnehmen
11. Beenden, wenn der restliche Speicherplatz gleich 0 ist (Speicherplatz = 5)
12. Zweitgrößte Datei (sofern es nicht die neu hinzugefügte ist) entfernen und Speicherplatz ermitteln (6)
13. Prüfen ob es eine Datei gibt, die <= dieser Grösse ist (ja: 6)
14. Wenn ja, diese Datei aufnehmen (4,6)
15. Beenden, wenn der restliche Speicherplatz gleich 0 ist (Speicherplatz = 0 Beenden)
16. Wenn der Speicherplatz größer ist als bei 3. entfernen der zuletzt hinzugefügten Datei und diese Grösse durch 2 teilen. Fortsetzen bei 6. bis kleinste Datei auf der DVD erreicht ist, oder Speicherplatz = 0 ist. Wenn Speicherplatz = 0 Beenden.
17. Freien Speicherplatz prüfen
18. Verteilung und Speicherplatzgrösse merken

19. Fortfahren analog 5. nur nicht durch 2, sondern durch 3 teilen.
20. Freien Speicherplatz prüfen
21. Verteilung und Speicherplatzgrösse merken
22. Kleinsten Speicherplatz von 4., 18. und 21.ermitteln und Beenden

Beenden bedeutet hier immer die gewählten Dateien zu markieren und dann zu beenden.

Falls jmd. Verbesserungsvorschläge für meinen Algorithmus hat, dann her damit

Mein Tipp:
Grenzwerte festlegen:
a) max. (Kapazität der DVD)
b) min. (max. - z.B. 50 MB - oder was auch immer)
Dann Array anlegen in dem nach Dateigrößen abwärts sortiert ist.
Dann jetzt einfach mehrere Schleifen nacheinander bzw. verschachtelt ablaufen lassen und zwar nach dem folgenden Schema:
1. größte Datei nehmen und schauen ob die Summe der Größen mit irgendeiner Datei (beginnend bei größter und nicht die gleiche) aus dem Array zwischen min und max liegt.
2. wenn ja: Dateien zum Brennen markieren (oder verschieben oder was auch immer) und Schleife(n) beenden
3. wenn Summe < min - weiteren Durchlauf starten um 3. Datei zuzufügen (bereits ausgewählte natürlich ausschließen - beliebig oft wiederholbar, 4., 5., … - sicherheitshalber Obergrenze einbauen!) bis 2. zutrifft
4. wenn Summe > max - nochmal von vorne anfangen beginnend mit 2. größter Datei (ggf. mit allen Elementen des Arrays - bis zum kleinsten)

Sofern Du genug Dateien hast kannst Du den Grenzbereich auch ziemlich klein halten und findest trotzdem immer eine passende Kombination.

Ich bin ja selten misstrauisch aber wegen 150 DVDs so ein Aufwand?

@buck: Danke für den Tipp. Das hört sich vernünftig an. Ich denke so werde ich es programmieren.