Optimierte Zahlengruppen bilden

[PeterPanino]

Hallo, ich habe ein kleines mathematisches Problem, das ich mit Delphi lösen möchte, vielleicht kann mir einer von den Mathematikern unter euch helfen?

Ich hab einen Menge von k Zahlen, z.B.: 31, 14, 84, 21, 31, 28, 99, 100, 211, 17, 28, 46, 145, 52, 82.

Diese Zahlen sollen nun so in Gruppen G1 - Gn aufgeteilt werden, dass folgende Bedingungen erfüllt sind:

0. Die Summe jeder Zahlengruppe Sn muss kleiner als ein vordefinierter Wert P sein.

1. Die Differenz zwischen Sn und P muss bei jeder Zahlengruppe möglichst klein sein.

1a. Die Summe der letzten Zahlengruppe Gn kann beliebig kleiner als P sein.

2. Die Summe der jeweiligen Differenzen zwischen der Gruppensumme Sn und P soll möglichst klein sein.

Ich könnte nun eine "Brut-Force"-Berechnung starten, indem ich alle möglichen Gruppenkombinationen durchprobiere, aber das würde bei einer etwas größeren Zahlenmenge ziemlich bald problematisch werden. Aber es muss sicher eine elegantere Lösung geben.

[Nikolas]

Woher kommt denn diese Aufgabe?

[PeterPanino]

Zitat:

Zitat von Nikolas

Woher kommt denn diese Aufgabe?

Von mir. Ich möchte damit ein bestimmtes Software-Problem lösen.

[Nikolas]

Willst du etwas brennen? Hier gibt's irgendwo ein Programm, mit dem man Dateien zerlegen kann. Damit könntest du immer eine kleine Gruppe nehmen und dann noch ein Stück von einer anderen Datei, um die CD vollzumachen.

Ohne sinnvollen Hintergrund ist die Frage etwas schwierig.

[PeterPanino]

Ich möchte Ordner und Dateien automatisch so auf Zielordner verteilen, dass die Ordner und Dateien in diesen Zielordnern dann möglichst optimiert (d.h. unter Verwendung von möglichst wenigen Rohlingen) jeweils auf CDs/DVDs gebrannt werden können. Die Ordner sollen nicht aufgeteilt werden und die Dateien schon gar nicht. Scheint aber ein komplexes mathematisches Problem zu sein.

[negaH]

Suche nach dem Rucksackproblem, dein Problem ist eine abgewandelte Form.

Gruß Hagen