nicht angemeldet
Moin,
ich habe mir folgende Aufgabe gestellt. Gegeben ist eine Liste von Wertepaaren. Ein Wertepaar besteht aus einem Punktwert und einem zugehörigen Preis. Nun möchte ich, bei fixem Budget, die Zusammenstellung finden, welche mir den optimalen Punktwert liefert.
Zum besseren Verständnis stelle man sich ein Manager-Spiel vor. Die Aufgabe besteht darin, aus der Vielzahl der verfügbaren Spieler, die Teilmenge (den eigenen Kader) mit der optimalen Punktausbeute auszuwählen und dabei das Budget einzuhalten.
Punkte Kosten
150 2.900 €
137 2.900 €
120 2.450 €
97 2.000 €
77 1.500 €
75 1.600 €
40 900 €
33 700 €
Gesamtbudget: 6.000 €
Mein Ansatz bestand darin, die Liste nach dem Preis-Leistungsverhältnis zu sortieren und anschließend von oben nach unten abzuarbeiten, bis mein Budget verbraucht ist. Mit dieser Methode erhalte einen Punktwert von 300. Allerdings ist mir eine andere gültige Zusammenstellung bekannt, die 302 Punkte bringt. Meine Methode leifert also nicht das optimale Ergebnis.
Meine Zweitidee besteht darin, alle möglichen Kombinationen durchzuspielen und anschließend den höchsten Punktwert abzulesen. Aber ehrlichgesagt weiß ich nicht mal, wie ich alle möglichen Kombinationen ermitteln kann.
Kann mir bitte jemand sagen, wie dieses Problem in Fachkreisen genannt wird, damit ich danach googlen kann. Oder vielleicht hat jemand sogar einen Lösungsansatz parat, den ich weiter verfolgen könnte? Ich würde mich dem Problem gern mit PHP nähern.
Noch Fragen?
Gruß der Buchhalter