Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Abgewandeltes Rucksackproblem (http://www.informatikerboard.de/board/thread.php?threadid=473)
Geschrieben von curious am 16.01.2009 um 16:28:
Abgewandeltes Rucksackproblem
Hallo,
kennt jemand einen Lösungsmöglichkeit für ein abgewandeltes Rucksackproblem:
Wenn der Gesamtnutzen der mitgenommenen Gegenständen nicht unabhängig von der Kombination der ausgewählten Objekten ist (Also nicht nur die Summe der einzelnen Nutzen, sondern eine Abhängigkeit besteht, z.B. ist es bei der Auswahl Orangensaft und Apfelsaft nicht so sinnvoll wie Apfelsaft und Brot).
Kennt jemand einen Ansatz oder wo ich dazu näheres finde? Vielen Dank!
Viele Grüße
Curious
Geschrieben von kiste am 16.01.2009 um 22:38:
Hallo,
eine gute Lösung wirst du sicherlich nicht finden da dieses Problem offensichtlich ebenfalls NP-vollständig ist.
Versuche einen der Standardansätze für Näherungslösungen(genetische Algos, simulated annealing etc.)
Geschrieben von curious am 17.01.2009 um 20:33:
Danke! Das mit der hohen Komplexität hatte ich leider auch befürchtet...
Viele Grüße
Curious
Forensoftware: Burning Board, entwickelt von WoltLab GmbH