Da die niedrigste Bewertung möglichst hoch sein soll, sollte zuerst versucht eine Route mit einer Mindestbewertung von 5.0 zu bilden. Scheitert dies wird es mit 4.9, 4.8, ..., 0.1 versucht. Das Routenbildung mit einer bestimmten Mindestbewertung kann aus zwei Gründen fehlschlagen:

innerhalb der 6 Stunden Fahrzeit gibt es kein Hotel mit der Mindestbewertung
an mehr als 4 Hotels muss gehalten werden

Umsetzung

Die Lösungsidee wird in C implementiert. Eine Hilfsfunktion der "advanced C standard library", die Textdateien ausliest, wird außerdem verwendet. Der Quelltext der Library ist im Ordner "lib/advanced_C_standard_library" oder online erhältlich. Das Programm erhält als Argumente eine beliebige Anzahl Dateipfade zu Eingabedateien. Mit einer for-Schleife wird über die Dateipfade iteriert. In der Schleife wird die Eingabedatei ausgelesen. Die Anzahl der Hotels und die Gesamtfahrzeit werden jeweils in einer Variable abgespeichert. Anschließend wird ein Array mit Strukturen, die Hotels darstellen, befüllt. In einer do-while-Schleife wird mit einer Bewertung von 5.0, 4.9, ..., 0.1 versucht eine Route zu bilden. Im Programm werden die Bewertungen als Integer dargestellt, wobei die Bewertung der Eingabedatei mit 10 multipliziert wird. Die Ausgabe ist wiederum im ursprünglichen Format. Wenn dies bei einer Bewertung erfolgreich ist, wird die Schleife beendet. In dieser Schleife ist wiederum eine for-Schleife, die über die Hotels iteriert, worin das letzte Hotel gespeichert wird, das mindestens die angestrebte Bewertung hat. Ist das Hotel allerdings mehr als 6 Stunden vom letzten Haltepunkt entfernt, muss das letzte Hotel verwendet werden, an dem das Halten möglich ist. Es sei denn es gibt kein Hotel mit der entsprechenden Bewertung oder es wurde bereits an mehr als drei Hotels gehalten. Dann muss mit der nächsten Bewertung fortgefahren werden. Nachdem eine Route gefunden wurde, wird diese ausgegeben und eventuell mit der nächten Eingabedatei fortgefahren.

Beispiele

Ergebnisse für die Beispieldaten:

hotels1.txt:
Entfernung vom Start: 347 Minuten, Bewertung: 2.7
Entfernung vom Start: 687 Minuten, Bewertung: 4.4
Entfernung vom Start: 1007 Minuten, Bewertung: 2.8
Entfernung vom Start: 1360 Minuten, Bewertung: 2.8
hotels2.txt:
Entfernung vom Start: 341 Minuten, Bewertung: 2.3
Entfernung vom Start: 700 Minuten, Bewertung: 3.0
Entfernung vom Start: 1053 Minuten, Bewertung: 4.8
Entfernung vom Start: 1380 Minuten, Bewertung: 5.0
hotels3.txt:
Entfernung vom Start: 360 Minuten, Bewertung: 1.0
Entfernung vom Start: 717 Minuten, Bewertung: 0.3
Entfernung vom Start: 1076 Minuten, Bewertung: 3.8
Entfernung vom Start: 1433 Minuten, Bewertung: 1.7
hotels4.txt:
Entfernung vom Start: 340 Minuten, Bewertung: 4.6
Entfernung vom Start: 676 Minuten, Bewertung: 4.6
Entfernung vom Start: 1032 Minuten, Bewertung: 4.9
Entfernung vom Start: 1316 Minuten, Bewertung: 4.9
hotels5.txt:
Entfernung vom Start: 317 Minuten, Bewertung: 5.0
Entfernung vom Start: 636 Minuten, Bewertung: 5.0
Entfernung vom Start: 987 Minuten, Bewertung: 5.0
Entfernung vom Start: 1286 Minuten, Bewertung: 5.0