Prof. Dr. R.
Laue
Dr. A. Kohnert
Diskrete Algorithmen
SS2005
Übungsblatt 11
Besprechung 8.7.05
URL: /axel/disc_ss05_blatt11.html
Abgabe zu Beginn der Übung.
Aufgabe 19- NASA (5+3 Punkte)
(nach Ross)
Ein Raumschiff soll zu einem entfernten Planeten aufbrechen. Der
Flightmanager muss entscheiden welche der m möglichen
Ausrüstungsgegenstände Ai an Bord genommen werden
soll. Jeder Ausrüstungsgegenstand verursacht Kosten ci
(natürlich >0). Mit den Ausrüstungsgegenständen kann
man aber Experimente Ej durchführen. Jedes Experiment
der insgesamt n möglichen bringt einen Gewinn von gj
(wieder >0). Für jedes Experiment ist eine Teilmenge der Menge
aller Ausrüstungsgegenstände nötig. Der Flightmanager
muss nun den Gesamtertrag der Mission maximieren, d.h. er muss
Ausrüstungsgegenstände so auswählen, dass die Summe
über die Erträge der Experimente abzüglich der Summe
über die Kosten der Ausrüstungsgegenstände maximal
wird.
Wie kann hier max flow / min cut helfen?
Lösen Sie folgendes Problem:
Es gibt 5 Ausrüstungsgegenstände zu Kosten (c1= 4,c2=5,c3=7,c4=1,c5=2)
.
Experiment 1 bringt 3 Einheiten Gewinn und benötigt
Ausrüstungsgegenstände 1 und 2.
Experiment 2 bringt 8 Einheiten Gewinn und benötigt
Ausrüstungsgegenstände 3 und 2.
Experiment 3 bringt 6 Einheiten Gewinn und benötigt
Ausrüstungsgegenstände 3, 4 und 2.
Experiment 4 bringt 3 Einheiten Gewinn und benötigt
Ausrüstungsgegenstände 4 und 5.
Welche Ausrüstungsgegenstände soll der Flightmanager an Bord
nehmen?