| JROppenheimer |
Rucksackproblem
Ich habe eine Frage zum allbekannten Rucksackproblem.
Ich habe eine Kapazität und eine Reihe Waren mit Gewicht und Wert.
Jetzt soll der Wert maximiert werden ohne die Kapazität zu überschreiten.
THEORETISCH hab ich verstanden wie das abläuft aber bei der praktischen Umsetzun hängts noch ein bisschen.
Ich könnte das ja rekursiv lösen, dann würden aber sehr viele Konfigurationen mehrfach berechnet werden. (Ware 1, Ware 2 hat ja den selben Wert und die selbe Last wie Ware 2, Ware 1)
Also wird das per dynamischer Programmierung gelöst.
Dabei legt man also Tabellen an, und speichert schon berechnete Werte ab, um diese dann nicht noch einmal berechnen zu müssen.
Ich weiss jetzt net so recht, wie ich das umsetzen soll.
also ich könnte jetzt hergehn und eine Tabelle erstellen, die Einträge für jede Restlast hat. Angefangen bei 0,1,2,3,....,T
dann könnte ich hergehn und sagen für Restgewicht 0 ist Optimalbeladung nichts. Für 1 ist es die fracht, die gewicht 1 hat und maximalen wert hat.... aber angenommen, das ist eine kontinuierliche Größe, dann ist das ja sehr Platzintensiv.
Also sage ich es müssen ja eigenldich nur DIE Restkapazitäten behandelt werden die sich aus Restkapzität - gewicht_i ergibt. Aber das führt ja wieder zu kombinatorischen Ausmaßen. Dann könnte man auch gleich hergehn und alle Möglichkeiten berechnen....
Ich hoffe es ist erkennbar, wo mein Problem liegt. Vlt kann mir einer helfen.
Danke im Voraus
*edit:
Mir ist gerade aufgefallen, dass es gar nicht nötig ist, ALLE kombinatorischen Möglichkeiten für das Rest Gewicht zu benutzen.
Man kann ja systematisch alle Waren angefangen bei der ersten durcharbeiten, denn wenn ware1 dabei ist in der optimalen Lösung ist es egal "WO" sie dabei ist, es zählt ledigllich, DASS sie dabei ist... |
