Beste Verteilung, Ausnutzung; Optimierung von Ordnern auf DVD

Hallo erstmal!

Wusste nicht genau wie ich das Thema nennen sollte, deswegen so ein komischer Titel ^^

Also mein Problem ist folgendes. Bin dabei ein Programm zu schreiben, das mir aus lauter Ordnern mit verschiedensten Dateien, diese so zusammenstellt, dass sie eine beschreibbare DVD möglichst perfekt ausnutzen. Reines herumprobieren ist nur mit geringer Ordneranzahl effektiv und wird mit steigender Anzahl bald sinnlos (z.B. 100 Ordner ~ 9,33e+157 Möglichkeiten ... sofern ich da richtig lieg ;)).

Also wird das ganze auf eine mathematische Optimierungsaufgabe hinauslaufen, bei denen ich aber nicht gerade gut bin. Könnt ihr mir da weiterhelfen wie ich dieses Problem angehen könnte ?

Danke
UNdY1n6

Rucksackproblem

Turing

NP hart!
Nimm lieber eine DVD mehr und mach es von Hand...

@UNdY1n6

Es handelt sich hierbei um ein Rucksackproblem (engl. knapsack problem),
welches mittels dynamischer Programmierung zumindest in pseudo-polynomieller
Zeit lösbar ist (siehe z.B. 'Knapsack Problem' in der englischen Wikipedia).

Für weitere Informationen zu dem Problem, "mathematische Hintergründe",
sowie ausführliche Pseudocodes zur Implementierung, siehe z.B. die sehr
ausführliche Seite der Operations Research Group an der Universität von Bologna.

Gruß,
Nidd

Turing

Es macht wirklich überhaupt keinen Sinn für dieses Problem ein Rucksackalgorithmus zu verwenden.

Die von Dir abgeschätzten 100! Möglichkeiten sind völlig überdimensioniert. Damit rechnest Du quasi aus, wie viele Möglichkeiten Du hast, jeden Ordner etwa auf eine nummerierte DVD zu brennen. Das willst Du sicher nicht.

Auch wenn es ein bisschen albern klingt, aber optimiere indem Du die Ordner alphabetisch auf die DVDs brennst. So lassen sie sich auch leichter wieder finden.