Rucksackproblem mit Abhängigkeiten

07.11.2008, 15:39	1of1	Auf diesen Beitrag antworten »
Rucksackproblem mit Abhängigkeiten Hallo zusammen! Das Rucksackproblem dürfte jedem hier ein Begriff sein, oder? Falls nicht grob: ich packe einen Rucksack, kann nur ein gewisses Gewicht tragen, die Gegenstände die ich einpacke wiegen etwas und nutzen mir etwas - was packe ich ein? Ich hab jetzt eine kleine Abwandlung: * ich habe keine obere Gewichtsschranke. * meine Gegenstände wiegen alle gleich viel (~ Kosten). * wenn ich einen Gegenstand einpacke, ändert sich jedoch der Nutzen eines anderen!!! Z.B.: Handy --> Handy-Ladegerät... (andersrum sinnlos). * ich packe nur ein, wenn der Nutzen höher ist als die Kosten / das Gewicht. So. Tja. Und nun? Hat jemand eine Idee, wie man das löst? Enumeration? Greedy-Algorithmus? ...?? Bin um jede Hilfe dankbar!!!!
10.11.2008, 13:30	1of1	Auf diesen Beitrag antworten »
Hat keiner eine Idee, wie man das formulieren und lösen könnte?
10.11.2008, 14:18	papahuhn	Auf diesen Beitrag antworten »
Im Informatikerboard wäre das wohl besser aufgehoben.
10.11.2008, 15:30	1of1	Auf diesen Beitrag antworten »
Mh, ok... touché... Ich werd's jetzt mit einem Greedy-Algorithmus lösen: in jedem Schritt den Nutzen von allen Objekten bestimmen, das beste auswählen, den Nutzen der verbleibenden berechnen, auswählen, ... Vorteil: das sind jeweils lokal optimale Teillösungen, womit die Gesamtlösung auch zumindest lokal optimal sein muss... Falls jemand dennoch eine bessere Idee hat?! Danke!!!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »