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

Hört sich nach einem Backtracking Algorithmus an, denke ich. Vielleicht hilft dir folgender Link?

Gruß Stefan

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.

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

Backtracking Meta:
(Du hast eine schon vorhandene unsortierte Permutation von Ordnern)

Code :

1 2 3 4 5

A: Ist ein Element Vorhanden?   Ja: Nimm das n.te Element und überprüfe ob Summe der gewählten Elemente größer max        Ja: Gehe zum nächsten Element in (A)        Nein: Nimm in die Folge auf und gehe zu nächsten Element in (A)   Nein: Wenn Folge nicht leer speichere Folge

Das mal so auf die Schnelle. Die Umsetzung sollte einfach sein.

Hallo,

also ich würde da einfach nen entsprechenden Genetischen Algorithmus drüber bügeln...

Gruß Tom

Ich hab mich gerade gestern mit dem Travelling Salesman Problem beschäftigt. Ist zwar nicht gerade das gleiche, aber geht trozdem in die gleiche Richtung. Wer interesse hat unter [1] hats nen interessanten Artikel.


Zu deinem Problem würd ich auch die Variante mit den absteigenden Grössen wählen. -> einfach, schnell und unkompliziert.
Und ob jetzt ein paar MB mehr oder weniger ausgenutzt werden können kommt bei den heutigen DVD Preisen auch nicht mehr draufan



1: http://www-i1.informatik.rwth-aachen...mus/algo40.php

Gruss

Also ich werde hauptsächlich die Methode von flashray benutzen und zusätzlich noch als Fleißarbeit ein Backtracking Möglichkeit einbauen. Mal will ja auch was lernen.