nicht angemeldet
Optimale Auswahl mit gegebenem Budget / Managerspiel
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
-
Nennt sich Rucksackproblem.
-
Nennt sich Rucksackproblem.
Danke, genau dieser Begriff war gesucht. Jetzt kann ich mich erstmal in die Pareto-Optimierung und ähnliches einlesen.
-
-
Mir fällt da der Solver von Excel ein. Damit löse ich immer solche Probleme.
Damit haben wir auch das Stichwort "Solver" für die Suchmaschine.-
Mir fällt da der Solver von Excel ein.
Danke für den Tipp. Den Solver hatte ich auch am Wickel, da ich viel mit Excel arbeite. Aber mich interessiert mehr die Vorgehensweise, denn das Ergebnis.
-