✔ Algorithmus zum Erzeugen eines Zahlenarrays

[mAu]

Hallo Tutorialianer,

ich bzw. ein Kommilitone hat folgendes Problem:

Wir haben ein Array mit Floatwerten, jetzt wollen wir ein zweites Array, welches zufällig gefüllt wird, einen Höchstbetrag aber nicht überschreiten darf.

input = array(1, 2, 3.5, 4, 5, 6, 7, 8, 10.5);

output = generateOutput(input);

output = array(1, 2, 5, 10.5); // Summe 18.5

Das zu erstellen ist prinzipiell kein Problem, aber es scheitert jetzt daran, immer das optimale Ergebnis zu erzielen, also das Array, welches am nächsten an den Maximalbetrag herankommt. Dabei dürfen die Werte aus dem Inputarray nur einmal benutzt werden.

Gibt's da einen Algorithmus oder wonach sollte ich am Besten schauen?

 

[Gumbo]

Dein Problem wird in der Litaratur als Rucksack-Problem bezeichnet.

 

[mAu]

Wunderbar, das trifft es genau Danke für den Link!

Edith sagt, dass es wunderbar geklappt hat. Hab den Pseudocode auf der Wikipediaseite quasi 1 zu 1 umgesetzt und hat wunderbar funktioniert.