Kombinationen für beste Annäherung an eine Zahl finden

A

Anime-Otaku

Erfahrenes Mitglied
Hallo,

ich hoffe der Titel war aussagekräftig genug...

Hier nochmal genau was ich meine:

Ich habe mehrere Zahlen (vielleicht maximal 300, aber i.d.R. unter 50).

Dann habe ich einen Maximalwert. Dieser darf nie überschritten werden. (Er darf ihn aber erreichen)

Nun würde ich gerne wissen, welche der 50 Zahlen ich addieren muss um am nähsten an den Maximalwert zu kommen.

Ich müsste, dazu ja jede Zahl mit jeder addieren (außer sich selbst natürlich) oder?

Wenn ja, wie kann ich das java technisch umsetzen oder gibt es da was mathematisches?

Ich bedanke mich schonmal für die hoffentlich zahlreichen Antworten:)
 
hi,
Versteh den Sinn Deiner Aufgabe nicht ganz, was ist denn z.B dein Maximalwert.
Hört sich an wie eine Reglungsaufgabe; wenn ein Schwellwert überschritten wird passiert irgendwas. Die Zahlen könnte man ja einfach in einer Schleife addieren!

Viele grüsse munuel
 
Ok, nochmal etwas genauer^^

Ich will ein Programm schreiben, welches mir Ordner so miteinander kombiniert, dass es auf eine CD/DVD bzw anderes Medium am besten passt.

Das Auslesen der Ordnergröße hab ich schon. Nun ist die Frage welche ganzen Ordner muss ich nehmen, dass es so gut wie möglich auf ein Medium passt und ich nicht die Ordner auseinander nehmen muss.

Dazu müsste ich ja jeden Ordner mit jeden Ordner usw. probieren bis ich sagen kann: "Bei dieser Kombination geht mir am wenigsten Speicherplatz auf dem Medium verloren."

Ich hoffe dadurch ist es klarer geworden auf was ich hinaus will. Ansonsten fragt mich gerne aus ;)

Das mit den Zahlen einfach addieren, wäre zwar wahrscheinlich die einfachste Möglichkeit, wäre aber sicher nicht komplett alles ausgeschöpft, oder?

Das mit dem Backtracking könnte es sein...jedoch hab ich keinen Plan wie ich das angehen soll, sorry.
 
Zuletzt bearbeitet:
Da Du hier ein Knapsack-Problem (Rucksack-Problem) beschreibst, welches NP-Vollständig ist, solltest Du ein bisschen nach Heuristiken googlen, die sich dem Problem angenommen haben.
Zu einem NP-Vollständigen Problem mit 50 bis 300 Variablen die optimale Lösung zu finden, kann schnell die Grenzen eines heimischen PCs sprengen.

Gruß hpvw
 
Hallo Anime-Otaku,

dein Vorhaben erinnert mich an das Münzproblem, das wir in Informatik mal gemacht haben. Da war das Ziel einen gegebenen Betrag aus möglichst wenig Münzen zusammenzustellen.

Mir fällt jetzt spontan folgendes ein.

i = 0 //Anzahl CD

1. Bestimme die Größen der vorhandenen Ordner.
2. Fange mit dem größten Ordner an, welche noch in die CD i passt und füge sie der CD i zu. Führe mit den nächst kleineren fort bis die CD i voll ist.
3. Falls noch Ordner vorhanden sind erhöhe i um 1 und mache weiter mit 2.

Vg Erdal
 
Ich bedanke mich und werde wahrscheinlich mehrere Algorithmen einbauen und diese Heuristik Sache ab ner bestimmten Anzahl von Ordner nicht zulassen.
 
Solange Du unter 10 Ordner hast, kannst Du (zum Beispiel mit allen Permutationen) optimal lösen.
Alles darüber solltest Du mit Heuristiken lösen.
Auch das, was flashray beschrieben hat ist eine Heuristik.

Gruß hpvw
 
Hallo,

nach nunmehr über einem Jahr habe ich wieder Zeit mich mit dem Thema zu beschäftigen.

Prinzipiell ist mir klar, was er machen soll, aber irgendwie stehe ich gerade auf der Leitung, wie ich die Permutation programmiertechnisch umsetzen soll.

Nochmal zur Wiederholung:
Jede Zahl soll mit jeder addiert werden, um die best mögliche Annäherung zu bekommen.
z.B. wir haben vereinfacht die Zahlen a b c, daraus ergeben sich folgende Möglichkeiten:
a,b,c,a+b,a+c,b+c,a+b+c

Daher haben wir (2^n)-1 Möglichkeiten. Mir ist klar, dass das schnell bei mehreren Ordnern aus dem Ruder gerät, aber es soll bis vielleicht 10 Ordner (muss man dann testen) zumindest die Möglichkeit geben.

Ich hoffe ihr könnt mir helfen, wie ich das code technisch umsetze.

Vielen Dank schonmal im voraus.
 
Hallo Anime-Otaku,

du brauchst hierfür keine Permutation!

Bestimme alle Ordner und deren größen, ordne sie der größe nach. Jetzt packst du einfach soviele große Ordner wie möglich in die CD. Dazu addierst du immer den Speicherplatzanspruch des nächstgrößeren und schaust ob diese immer noch passt. Wenn ja, weiter mit der Strategie. Wenn nein, dann weisst du das du alle Ordner bzw. Dateien außer dem letzten in die CD passen.

Diese kannst du brennen. Ebenso verfährst du mit dem Rest.


Vg Erdal
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück