Prof. Dr. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 20. November 2001
Christian Ehrhardt Blatt 5






Allgemeine Informatik 3 (WS 2001/2002)


Abgabetermin 27.11. 2001 vor den Übungen

Da steh' ich nun ich armer Tor ... (10 Punkte)

... und bin so reich als wie zu vor.
Sie sind gerade frisch in den Tresorraum einer Bank eingebrochen und fangen an so viele Goldbarren einzupacken, wie Sie eben nur mitnehmen können. Leider müssen Sie feststellen, daß Sie nicht alle Barren mitnehmen können. Der Hersteller des Handwagens, mit dem Sie das Gold abtransportieren wollen, hat Ihnen garantiert, daß der Wagen 5000 Feinunzen (ca. 156kg) transportieren kann. Dieses Gewicht wollen Sie auf keinen Fall überschreiten, da sonst Ihre Garantie erlischt. Dennoch erinnern Sie sich an eine alte schwäbische Weisheit (``Mr nemmt was mr kriaga ka'') und beschließen daher, die Barren, die Sie mitnehmen wollen, so auszuwählen, daß das Gesamtgewicht möglichst nahe an 5000 Feinunzen kommt. Wegen der schon erwähnten Garantie darf dieses Gewicht aber keinesfalls überschritten werden.
Ihr Programm soll also von der Standardeingabe zunächst die Anzahl N der vorhandenen Barren (bis zu 100) und anschließend das Gewicht der einzelnen Barren in Unzen (N ganze Zahlen zwischen 1 und 5000) einlesen. Anschließend soll Ihr Programm berechnen, welche Barren Sie mitnehmen müssen und wieviele Feinunzen Gold Sie mit dieser Auswahl tatsächlich abtransportieren können. Wenn es mehrere Möglichkeiten gibt, die Goldbarren optimal auszuwählen, genügt es irgend eine anzugeben.

Anleitung

Beachten Sie, daß Ihr Programm auch in endlicher Zeit terminieren soll. Damit ist es nicht möglich, alle bis zu $2^{100}$ Möglichkeiten auszuprobieren. Sie müssen sich also etwas schlaueres überlegen.
Als Faustregel für die Abschätzung der tatsächlichen Laufzeit können Sie sich überlegen wie oft das am häufigsten ausgeführte Stück Ihres Programms tatsächlich durchlaufen wird. Liegt dieser Wert bei einer Million, dann können Sie mit einer Laufzeit von ca. einer Sekunde rechnen.
Um zu einer akzeptablen Laufzeit zu kommen betrachten Sie die Funktion $f(u,k)$, die genau dann den Wert $1$ annehmen soll, wenn es eine Auswahl aus den ersten $1 \ldots k$ Barren gibt, mit der exakt ein Gewicht von $u$ Feinunzen erreicht wird. In allen anderen Fällen soll f den Wert $0$ haben. Überlegen Sie sich anschließend, wie Sie die Werte von $f(u,k+1)$ berechnen können, wenn die Werte $f(u,k)$ bereits bekannt sind. Was läßt sich über $f(u,0)$ sagen? Wie kann eine vollständige Wertetabelle für die Funktion $f$ verwendet werden, um zunächst das gesuchte Gesamtgewicht in Unzen und anschließend eine dazu passende Auswahl von Goldbarren zu bestimmen?
Wenn Sie zusätzlich noch beachten, daß aus $f(u,k)=1$ auch $f(u,k+1) = 1$ folgt (warum?), können Sie mit einer eindimensionalen Wertetabelle auskommen.

Testdaten

Für dieses Programm gibt es wieder Testdaten. Ihr Programm sollte in der Lage sein, alle Testfälle innerhalb weniger Sekunden zu lösen. Laufzeiten von mehr als einer Minute pro Testfall sollten auf keinen Fall vorkommen. Aufeinanderfolgende Testfälle sind der besseren Lesbarkeit in der Eingabedatei durch Leerzeilen getrennt. Beachten Sie, daß die erste Zahl jedes Testfalls angibt, wie viele Barren in diesem Testfall vorkommen.