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.
Noch keine Stimmen abgegeben
Noch keine Kommentare

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)?