C++ Programmieraufgabe: Das Rucksackproblem

Das Rucksackproblem gehört zur Klasse der Optimierungsprobleme. Dabei sollen aus einer Menge von Gegenständen diejenigen in den Rucksack gepackt werden, die den Wert seines Inhaltes maximieren. Für kleine Anzahlen von Gegenständen kann man die optimale Lösung leicht erraten. Für sehr große Anzahlen kann ein Algorithmus, der alle möglichen Bepackungen durchprobiert, unzumutbare Rechenzeit beanspruchen.

walter
brute force Algorithmus Rucksackproblem greedy Algorithmus C++ Programmieraufgabe
Inhaltsverzeichnis

Einordnung des Artikels

Die Problemstellung

Gegeben sind n Objekte, wobei jedem Objekt ein Volumen V(i) und ein Wert W(i) zugeordnet ist, i = 1,..., n.

Zur Verfügung steht ein Rucksack mit Volumen R. Aus den n Gegenständen soll eine Teilmenge ausgewählt werden mit folgenden Eigenschaften:

  1. Die Gegenstände passen in den Rucksack, also die Summe der V(i) ist kleiner oder gleich R. (Auf die Form der Gegenstände soll dabei nicht geachtet werden.)
  2. Der Gesamtwert soll möglichst groß sein.

Abbildung 1: Oben ist der Rucksack mit Volumen R gezeigt sowie die 5 Gegenstände mit ihrem jeweiligen Wert. Unten sind zwei mögliche Bepackungen dargestellt: Bei der Ersten ist der Rucksack genau gefüllt, der Gesamtwert der enthaltenen Gegenstände beträgt 18. Bei der zweiten Bepackung ist der Rucksack nicht ganz gefüllt (es gibt keinen Gegenstand, der noch hineinpassen würde), aber der Gesamtwert ist mit 20 größer als 18.Abbildung 1: Oben ist der Rucksack mit Volumen R gezeigt sowie die 5 Gegenstände mit ihrem jeweiligen Wert. Unten sind zwei mögliche Bepackungen dargestellt: Bei der Ersten ist der Rucksack genau gefüllt, der Gesamtwert der enthaltenen Gegenstände beträgt 18. Bei der zweiten Bepackung ist der Rucksack nicht ganz gefüllt (es gibt keinen Gegenstand, der noch hineinpassen würde), aber der Gesamtwert ist mit 20 größer als 18.

Bei kleiner Anzahl n lässt sich die optimale Lösung durch Ausprobieren schnell finden, aber bei großen Anzahlen n gibt es zu viele Möglichkeiten, die man durchprobieren müsste. Sie sollen hier einige Algorithmen formulieren, die — mehr oder weniger gut — in der Lage sind für beliebige Eingabedaten die optimale Lösung zu finden.

Programmieraufgaben

  1. Erzeugen Sie geeignete Testdaten, mit denen Sie später Ihre Algoritmen testen können. Die Algoritmen sollen dann aber so geschrieben werden, dass beliebige Eingabedaten verarbeitet werden.
  2. Schreiben Sie ein Funktion, die zu vorgegebenen Werten für R, die Volumina V(i) und die Werte W(i), i = 1,..., n, alle möglichen Bepackungen des Rucksacks ausgibt (also Summe der Volumina ist kleiner gleich R) und den Gesamtwert berechnet. Die Ausgabe soll sortiert erfolgen, also wertvollste Bepackung zuerst.
  3. Schreiben Sie eine Funktion (greedy Algoritmus, greedy = gierig), die im nächsten Schritt immer den wertvollsten noch zur Verfügung stehenden Gegenstand in den Rucksack packt.
  4. Schreiben Sie eine Funktion (greedy Algoritmus 2. Ordnung), die im nächsten Schritt immer den wertvollsten oder den zweit-wertvollsten Gegenstand in den Rucksack packt. Ausgegeben werden sollen wieder alle möglichen Bepackungen, sortiert nach ihrem Wert.
  5. Überlegen Sie sich einen weiteren Algorithmus, der zwar nicht alle Möglichkeiten berechnet, der aber dennoch in der Lage ist, der optimalen Lösung möglichst nahe zu kommen.
  6. Untersuchen Sie die Komplexität der Algorithmen: Versuchen Sie abzuschätzen, wie die Rechenzeit zunimmt, wenn die Anzahl der Gegenstände n erhöht wird. Welche der Algorithmen besitzen eine Rechenzeit T(n), die proportional ist zu:
    • n
    • zu einer Potenz p von n, also np
    • zu en (exponentielle Abhängigkeit)?