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.
Inhaltsverzeichnis
Noch keine Stimmen abgegeben
Noch keine Kommentare
Einordnung des Artikels
- EinfĂŒhrung in die Informatik
- C++ Programmieraufgaben
- Das Rucksackproblem
- C++ Programmieraufgaben
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:
- 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.)
- Der Gesamtwert soll möglichst groà sein.
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
- 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.
- 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.
- 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.
- 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.
- Ă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.
- 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)?