Suche Home Einstellungen Anmelden Hilfe

	Didaktik der  Informatik

Zwischen der alten Mutter Erde und unserem neu besiedelten Planeten Erde2 wird eine Passagierfähre mit begrenzter Ladefähigkeit eingerichtet, die jedoch nur einmal pro Tag von der Erde zur Erde 2 und zurück fliegt. Um die Fähre optimiert zu nutzen, müssen sich alle Passagiere am Vortag unter Angabe ihres Gewichtes angemeldet haben. Alle Passagiere haben das gleiche Recht die Fähre zu nutzen, aber Diplomaten, Adlige, WissenschaftlicheMitarbeiter und einige andere werden bevorzugt behandelt (d. h. es werden Prioritäten vergeben und man versucht die Ladung so "wertvoll" wie möglich zu machen). Man könnte natürlich die Ladung auch möglichst "nicht-wertvoll" zusammenstellen, um Attentate auf Fähren weniger lohnend erscheinen zu lassen. Passagiere, die an einem Tag nicht befördert werden konnten, bekommen für den nächsten Tag eine höhere Priorität.

Schreiben Sie ein Programm in ML, welches bei Eingabe der ganzzahligen Passagierdaten (Nr, Abflugort, Gewicht, Priorität) und der ganzzahligen, maximalen Ladekapazität der Fähre die Passagiere ausgibt, die den aktuellen Flug benutzen dürfen, und die Daten (mit erhöhter Priorität) der Passagiere ausgibt, die nicht mitfliegen durften, so dass diese als Eingabe für einen erneuten Aufruf des Programm genutzt werden können.

Bsp. (max. Ladekapazität: 11, Abflugort: Erde2):

Passagiernr.	Gewicht	Priorität
1	1	2
2	3	4
3	4	3
4	7	5

Lösung: Passagiere mit der Nr. 1,2,4 fliegen heute
             nicht-fliegende Passagiere: (3,Erde2,4,3)

Stichworte: Rucksackproblem, NP-vollständiges Problem,Entscheidungsbaum, Branch&Bound, Dynamische Programmierung, Divde&Conquer, Laufzeit

Literatur: Duden Informatik, Algorithmen-Sedgewick S. 673ff, Artikel Bubeck zur IOI97, C't Artikel aus Heft 10/1997 S. 336-345  

Ergebnisse der Projektgruppe  

Benutzer: Gast • Besitzer: mthomas • Zuletzt geändert am: