====== Das Rucksackproblem (Knapsack Problem) ======
===== Problemstellung =====
Das Rucksackproblem (englisch "Knapsack Problem") ist ein beliebtes Beispiel um Algorithmen zu üben. Dabei werden Gegenstände (definiert über ein Volumen und einen Wert) in einen Rucksack gepackt. Ziel ist es, einen möglichst hohen Wert in den Rucksack zu packen. Die Formen der Gegenstände und des Rucksacks werden dabei vernachlässigt: Solang das übrige Volumen im Rucksack größer als jenes des Gegenstandes ist, passt der Gegenstand auch in den Rucksack.
===== Eingabe =====
Während wir eine möglichst effiziente Lösung für das Problem suchen, verwenden wir folgende Eingabegrößen:
^ Variable ^ Wert ^
| Volumen des Rucksacks (V) | 30 |
| Anzahl aller Gegenstände (n) | 10 |
Die Gegenstände haben folgende Eigenschaft, geordnet nach Volumen und dann nach Wert:
^ Gegenstandsnummer ^ Volumen (v) ^ Wert (w) ^
| 1 | 5 | 8 |
| 2 | 5 | 8 |
| 3 | 6 | 6 |
| 4 | 8 | 5 |
| 5 | 10 | 10 |
| 6 | 11 | 5 |
| 7 | 12 | 10 |
| 8 | 15 | 17 |
| 9 | 15 | 20 |
| 10 | 30 | 20 |
Eingegeben werden die Daten in folgendem Format:
V n
v[0] w[0]
v[1] w[1]
v[2] w[2]
v[3] w[3]
...
v[n - 1] w[n - 1]
Oder speziell mit unseren Testdaten:
30 10
5 8
5 8
6 6
8 5
10 10
11 5
12 10
15 17
15 20
30 20
===== Greedy =====
Der erste Ansatz der einem Anfänger einfällt, ist meistens ein Greedy-Algorithmus. Greedy bedeutet, dass man eine Bewertungsfunktion für die - im aktuellen Zustand - optimale Auswahl verwendet. In diesem Fall wäre das die Relation zwischen Volumen und Wert eines Gegenstandes. Je höher der Wert pro Volumen, desto eher wird der Gegenstand eingepackt. Unsere Bewertungsfunktion ist also einfach die Division des Wertes durch das jeweilige Volumen. \\
Wir erweitern die Tabelle um unsere Greedy-Bewertung und sortieren sie danach absteigend nach unserer Bewertung und dem Volumen:
^ Gegenstandsnummer ^ Volumen ^ Wert ^ Wert / Volumen ^
| 1 | 5 | 8 | 1.6 |
| 2 | 5 | 8 | 1.6 |
| 9 | 15 | 20 | 1.333 |
| 8 | 15 | 17 | 1.133 |
| 5 | 10 | 10 | 1 |
| 3 | 6 | 6 | 1 |
| 7 | 12 | 10 | 0.833 |
| 10 | 30 | 20 | 0.667 |
| 4 | 8 | 5 | 0.625 |
| 6 | 11 | 5 | 0.455 |
Das absteigende Sortieren nach dem Volumen erscheint auf den ersten Blick vielleicht nicht sinnvoll. Gegenstände mit gleichem Greedy-Wert, aber höheren Volumen belegen mehr Platz mit einer hohen Werte-Dichte. Alle Gegenstände danach haben höchstens den gleichen Greedy-Wert, aber niemals einen höheren. Deshalb sollten Gegenstände mit diesem Greedy-Wert so viel Platz wie möglich belegen.\\
Nun nehmen wir solange den am besten bewerteten Gegenstand, bis wir keinen Platz mehr im Rucksack haben. In diesem Fall wären das die Gegenstände 1, 2, und 9 mit einem Gesamtvolumen von 25 (5 + 5 + 15) und einem Gesamtwert von 36 (8 + 8 + 20).\\
In Code würde unsere Lösung so aussehen:
// g++ knapsack_greedy.cpp
#include
#include
// Berechnet den Greedy-Wert aller Gegenstände
void rateItems();
// Sortiert Gegenstände nach Greedy-Wert und Volumen (basiert auf Selectionsort)
void sortItems();
// Maximale Anazahl an Gegenständen
const int maxN = 300;
// Maximales Volumen des Rucksacks
const int maxV = 1000;
// Volumen des Rucksacks
int V;
// Anzahl an Gegenständen
int n;
// Volumen der einzelnen Gegenstände
int v[maxN];
// Werte der einzelnen Gegenstände
int w[maxN];
// Maximaler Wert des Rucksacks
int maxValue = 0;
// Greedy-Bewertung der einzelnen Gegenstände
float greedyValues[maxN];
int main()
{
// Eingabe der Daten
scanf( "%d %d", &V, &n );
for( int i = 0; i < n; i++ )
scanf( "%d %d", &( v[i] ), &( w[i] ) );
// Gegenstände bewerten und sortieren
rateItems();
sortItems();
// Die besten (nach Greedy-Bewertung) Gegenstände auswählen, die noch Platz haben
for( int i = 0; i < n; i++ )
{
// Prüfen, ob der Gegenstand noch Platz im Rucksack hat
if( V - v[i] >= 0 )
{
maxValue += w[i];
V -= v[i];
}
}
printf( "%d\n", maxValue );
return 0;
}
void rateItems()
{
for( int i = 0; i < n; i++ )
greedyValues[i] = (float) w[i] / (float) v[i];
}
void sortItems()
{
int max;
int tmp;
for( int i = 0; i < n; i++ )
{
max = i;
for( int j = i + 1; j < n; j++ )
{
if( greedyValues[j] > greedyValues[max] )
max = j;
else if( greedyValues[j] == greedyValues[max] && v[j] > v[max] )
max = j;
}
if( max != i )
{
tmp = v[max];
v[max] = v[i];
v[i] = tmp;
tmp = w[max];
w[max] = w[i];
w[i] = tmp;
}
}
}
===== Rekursion =====
Unser Greedy-Algorithmus ist schon ganz schön. Aber ist das wirklich die beste Lösung? Das kann man nicht sicher sagen. Unsere Lösung ist eine Annäherung, aber nicht zwingend die optimale Lösung, welche stark von den Eingabedaten abhängig ist. Diese können wir nur finden, indem wir alle Möglichkeiten ausprobieren. Wir müssen jede mögliche Kombination aus Gegenständen im Rucksack durchprobieren und den maximalen Wert finden. Man nennt dieses Vorgehen auch [[glossary:combinatorics|kombinatorische Optimierung]]. Das ist zwar viel aufwändiger als unser Greedy-Algorithmus, aber die einzige Möglichkeit um ganz sicher das beste Ergebnis zu liefern.\\
Für jeden Gegenstand haben wir 2 Möglichkeiten: In den Rucksack oder nicht. Wahr oder falsch. Egal welche Entscheidung wir treffen, für den nächsten Gegenstand haben wir wieder die selben Auswahlmöglichkeiten. Für solche Entscheidungen bietet sich eine [[algo:recursion|Rekursion]] in Form eines [[struct:tree:start#binaere_baeume|binären Baumes]] an. \\
{{:algo:recursion.png?|}}
\\
\\
Grafisch würden die ersten 3 Schritte unseres Baumes also so aussehen: \\
{{:algo:recursionsteps.png?|}}
\\
In jedem Rekursionsschritt werden 2 Werte berechnet: Der maximale Wert ohne den aktuellen Gegenstand und jener mit dem aktuellen Gegenstand. Beim letzten Gegenstand endet die Rekursion. Es wird nur noch geprüft, ob der Gegenstand allein in den Rucksack passt und der Wert mit und ohne den Gegenstand (im letzteren Fall logischerweise immer 0) wird zurückgegeben. Alle darüberliegenden Rekursionen befolgen die gleichen Schritte und addieren ihr Ergebnis gegebenenfalls zum vorherigen. Der höhere der beiden Werte (mit bzw. ohne aktuellen Gegenstand) wird zurückgegeben. Dadurch erhalten wir bei der Wurzel automatisch das gesuchte Maximum.\\
Eine Implementierung könnte so aussehen:
// g++ knapsack_recursive.cpp
#include
#include
#include
// currentVolume: Das restliche (freie) Volumen im Rucksack
// i: Aktueller Gegenstand
// Return value: Maximaler Wert mit bzw. ohne den aktuellen Gegenstand
int knapsack( const int currentVolume, const int i );
// Maximale Anazahl an Gegenständen
const int maxN = 300;
// Maximales Volumen des Rucksacks
const int maxV = 1000;
// Volumen des Rucksacks
int V;
// Anzahl an Gegenständen
int n;
// Volumen der einzelnen Gegenstände
int v[maxN];
// Werte der einzelnen Gegenstände
int w[maxN];
int main()
{
// Eingabe der Daten
scanf( "%d %d", &V, &n );
for( int i = 0; i < n; i++ )
scanf( "%d %d", &( v[i] ), &( w[i] ) );
// Berechnung und Ausgabe
printf( "%d\n", knapsack( V, 0 ) );
return 0;
}
int knapsack( const int currentVolume, const int i )
{
if( i < n )
{
// Berechne Wert ohne den aktuellen Gegenstand
int a = knapsack( currentVolume, i + 1 );
// Berechne Wert mit dem aktuellen Gegenstand, wenn noch Platz dafür ist
int b = 0;
if( currentVolume - v[i] >= 0 )
b = w[i] + knapsack( currentVolume - v[i], i + 1 );
// Maximum der Berechnung wird gespeichert und zurückgegeben
return std::max( a, b );
}
return 0;
}
Wir sehen bei der Ausführung, dass unser Greedy-Algorithmus zwar eine relativ gute Lösung ergeben hat, aber doch nicht das Optimum von 38.
===== Dynamische Programmierung =====
Nun haben wir ganz sicher das beste Ergebnis. Jedoch ist unser Algorithmus im Vergleich zur Greedy-Lösung viel langsamer geworden, da wir immer alle Möglichkeiten durchprobieren. Da unsere Rekursion auf einem Binärbaum basiert (jeder nicht-Blatt Knoten hat 2 Folge-Rekursionen), haben wir insgesamt bis zu 2n Rekursionsaufrufe. Bei 10 sind das lediglich 1024, was bei modernen Rechnern kein Problem darstellt. Bei 100 Gegenständen sind das jedoch bereits 1267650600228229401496703205376 Rekursionsaufrufe! Wenn wir nur bedenken, dass für jeden Funktionsaufruf ein Zeiger mit der Rücksprungadresse mit 8 bzw. 4 Byte auf den Stack gelegt wird, sollte uns sofort klar werden, dass unser Algorithmus mit einer solch großen Anzahl an Möglichkeiten nicht umgehen kann. Von der Dauer der Berechnung und der Funktionsaufrufe mal ganz abgesehen. Wir müssen unseren Algorithmus also noch optimieren. Konkret müssen wir die Anzahl an Rekursionaufrufen verringern. Dazu sehen wir uns die Grafik von vorhin nochmals an: \\
{{:algo:recursionsteps.png?|}}
\\
Fällt etwas auf? Bereits beim 3. Rekursionsschritt haben wir 2 mal die gleiche Ausgangssituation. 2 mal haben wir aufgrund der identischen Volumen der beiden ersten Gegenstände ein verbrauchtes Volumen von 5 und ein restliches Volumen von 25. Die nachfolgenden Operationen für beide Fälle sind identisch, da auch die Ausgangslage gleich ist. Daher werden wir auch für beide Fälle das gleiche Ergebnis erhalten. Was bedeutet das nun für uns? Wenn wir uns das Ergebnis nach dem ersten Durchlauf dieser Ausgangslage speichern und beim 2. mal lediglich wieder abrufen anstatt neu zu berechnen, können wir uns bereits beim 2. Rekursionsschritt ein Viertel des restlichen Rekursionsbaumes ersparen! \\
{{:algo:recursion_dynamic.png?|}}
\\
Je mehr Gegenstände wir haben, desto höher ist auch die Wahrscheinlichkeit Werte doppelt zu berechnen. Um diese Eigenschaft auszunutzen, wenden wir das Prinzip der Dynamisierung an. Wir speichern uns bereits berechnete Werte in einem 2-dimensionalen Array, den wir mit -1 initialisieren. Vor jeder Berechnung fragen wir zuerst, ob für diese Ausgangssituation bereits eine Berechnung durchgeführt wurde (ob der Wert am aktuellen Index nicht -1 ist). Ist das der Fall, geben wir einfach den bereits berechneten Wert zurück und brechen die aktuelle Rekursion ab. Ist der Wert noch nicht vorhanden, wird er berechnet und im Array gespeichert. \\
Wie definieren wir nun eine "identische Ausgangsposition"? Eine identische Ausgangsposition haben wir dann, wenn wir beim gleichen Gegenstand sind und das gleiche Rest-Volumen vorhanden haben. Der erste Index unseres Dynamisierungs-Arrays ist also der Index des aktuellen Gegenstandes, der zweite das freie Volumen. Da Array-Indizes bekanntlich bei 0 zu zählen beginnen, müssen wir unseren Array in der 2. Dimension um 1 größer machen. Ansonsten würden wir einen Fehler beim ersten Aufruf bekommen, da das Gesamtvolumen die Arraygröße überschreitet.\\
Implementierung:
// g++ knapsack_dynamic.cpp
#include
#include
#include
// currentVolume: Das restliche (freie) Volumen im Rucksack
// i: Aktueller Gegenstand
// Return value: Maximaler Wert mit bzw. ohne den aktuellen Gegenstand
int knapsack( const int currentVolume, const int i );
// Maximale Anazahl an Gegenständen
const int maxN = 300;
// Maximales Volumen des Rucksacks
const int maxV = 1000;
// Anzahl an Byte für unseren Dynamisierungs-Array
const int resultLength = ( maxV + 1 ) * sizeof( int );
// Volumen des Rucksacks
int V;
// Anzahl an Gegenständen
int n;
// Volumen der einzelnen Gegenstände
int v[maxN];
// Werte der einzelnen Gegenstände
int w[maxN];
// Gespeicherte Ergebnisse von bisherigen Berechnungen
int results[maxN][maxV + 1];
int main()
{
// Eingabe der Daten
scanf( "%d %d", &V, &n );
for( int i = 0; i < n; i++ )
scanf( "%d %d", &( v[i] ), &( w[i] ) );
// Initialisierung der Dynamisierungs-Matrix mit -1
for( int i = 0; i < n; i++ )
memset( results[i], -1, resultLength );
// Berechnung und Ausgabe
printf( "%d\n", knapsack( V, 0 ) );
return 0;
}
int knapsack( const int currentVolume, const int i )
{
// Prüfen, ob ein gültiger Index übergeben wurde
if( i < n )
{
// Prüfen, ob der Wert bereits berechnet wurde.
if( results[i][currentVolume] != -1 )
return results[i][currentVolume];
// Berechne Wert ohne den aktuellen Gegenstand
int a = knapsack( currentVolume, i + 1 );
// Berechne Wert mit dem aktuellen Gegenstand, wenn noch Platz dafür ist
int b = 0;
if( currentVolume - v[i] >= 0 )
b = w[i] + knapsack( currentVolume - v[i], i + 1 );
// Maximum der Berechnung wird gespeichert und zurückgegeben
results[i][currentVolume] = std::max( a, b );
return results[i][currentVolume];
}
return 0;
}
\\
Die gleiche Rekursion in kürzerer Schreibweise sieht so aus:
int knapsack( const int currentVolume, const int i )
{
if( i < n )
{
if( results[i][currentVolume] != -1 )
return results[i][currentVolume];
return results[i][currentVolume] = std::max( knapsack( currentVolume, i + 1 ),
( currentVolume - v[i] >= 0 )
? ( w[i] + knapsack( currentVolume - v[i], i + 1 ) )
: 0 );
}
return 0;
}
===== Ausgwewählte Gegenstände über Backtracking feststellen =====
Nun wäre es interessant zu wissen, welche Gegenstände sich bei der optimalen Lösung im Rucksack befinden. An diesem Punkt sollten wir uns ganz bewusst werden, was die Dynamisierungsmatrix überhaupt darstellt. Sie speichert den maximalen Wert im Rucksack an einem bestimmten Gegenstands-Index und Volumen. Sehen wir uns die Dynamisierungsmatrix an (Die Matrix wird aus optischen Gründen etwas kleiner gemacht: maxN = 10, maxV = 30):
// g++ knapsack_matrix.cpp
#include
#include
#include
// currentVolume: Das restliche (freie) Volumen im Rucksack
// i: Aktueller Gegenstand
// Return value: Maximaler Wert mit bzw. ohne den aktuellen Gegenstand
int knapsack( const int currentVolume, const int i );
// Maximale Anazahl an Gegenständen
const int maxN = 10;
// Maximales Volumen des Rucksacks
const int maxV = 30;
// Anzahl an Byte für unseren Dynamisierungs-Array
const int resultLength = ( maxV + 1 ) * sizeof( int );
// Volumen des Rucksacks
int V;
// Anzahl an Gegenständen
int n;
// Volumen der einzelnen Gegenstände
int v[maxN];
// Werte der einzelnen Gegenstände
int w[maxN];
// Gespeicherte Ergebnisse von bisherigen Berechnungen
int results[maxN][maxV + 1];
int main()
{
// Eingabe der Daten
scanf( "%d %d", &V, &n );
for( int i = 0; i < n; i++ )
scanf( "%d %d", &( v[i] ), &( w[i] ) );
// Initialisierung der Dynamisierungs-Matrix mit -1
for( int i = 0; i < n; i++ )
memset( results[i], -1, resultLength );
// Berechnung und Ausgabe
printf( "%d\n", knapsack( V, 0 ) );
// Ausgabe der Gegenstands-Indizes als 1. Zeile
printf( " " );
for( int i = 0; i < maxN; i++ )
printf( "%2d ", i );
printf( "\n" );
// Ausgabe der Volumen als 1. Spalte und Werte in der Matrix
for( int i = 0; i < maxV + 1; i++ )
{
// Volumen ausgeben
printf( "%2d ", i );
// Werte in der aktuellen Zeile ausgeben
for( int j = 0; j < maxN; j++ )
printf( "%2d ", results[j][i] );
printf( "\n" );
}
return 0;
}
int knapsack( const int currentVolume, const int i )
{
if( i < n )
{
if( results[i][currentVolume] != -1 )
return results[i][currentVolume];
return results[i][currentVolume] = std::max( knapsack( currentVolume, i + 1 ),
( currentVolume - v[i] >= 0 )
? ( w[i] + knapsack( currentVolume - v[i], i + 1 ) )
: 0 );
}
return 0;
}
Der Code liefert unter dem Ergebnis folgende Ausgabe der Dynamisierungs-Matrix:
| ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^
^ 0 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 |
^ 1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 2 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 3 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 |
^ 4 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 5 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 |
^ 6 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 |
^ 7 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 8 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 |
^ 9 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 10 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 11 | -1 | -1 | -1 | -1 | 10 | 5 | 0 | 0 | 0 | 0 |
^ 12 | -1 | -1 | -1 | -1 | 10 | 10 | 10 | 0 | 0 | 0 |
^ 13 | -1 | -1 | -1 | -1 | -1 | -1 | 10 | 0 | 0 | 0 |
^ 14 | -1 | -1 | -1 | 10 | 10 | 10 | 10 | 0 | 0 | 0 |
^ 15 | -1 | -1 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 0 |
^ 16 | -1 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 17 | -1 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 18 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 20 | 20 | 0 |
^ 19 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 20 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 21 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 22 | -1 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 23 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 24 | -1 | -1 | -1 | 25 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 25 | -1 | 30 | 30 | 30 | 30 | 20 | 20 | 20 | 20 | 0 |
^ 26 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 27 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 28 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 29 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 30 | 38 | 38 | 37 | 37 | 37 | 37 | 37 | 37 | 20 | 20 |
Spalten sind Gegenstände (Gegenstandsnummer - 1), Zeilen die jeweiligen (belegten) Volumen. Die erste Spalte ist der Volumen-Index, die erste Zeile der Gegenstands-Index.\\
Wir finden unser optimales Ergebnis in der ersten Spalte, in der letzten Zeile. Warum gerade dort? Der Rekursionbaum geht zuerst durch alle Äste bis an die Blätter und kommt dann zur Wurzel zurück. Schritt für Schritt werden dann die Werte in die Matrix eingefügt, der Wert beim ersten Gegenstand ganz zum Schluss. Da man in allen Rekursionen davor immer das Maximum genommen hat, erhält man hier das größte Maximum aller möglichen Rekursionswege (Anmerkung: In results[1][30] steht ebenfalls das Maximum. Das hat einen ganz einfachen Grund: Gegenstand 0 und 1 sind identisch. Da nur einer der beiden Gegenstände ausgewählt wird, kann das Maximum mit beiden Gegenständen gebildet werden.). In unserem Fall wird das Volumen des Rucksacks vollständig belegt, deshalb steht der Wert in der letzten Zeile.\\
So, nun wissen wir aber nicht wirklich mehr als zuvor. Wie kann man prüfen, ob der erste Gegenstand (Volumen 5, Wert 8) in den Rucksack gegeben wurde? Ganz einfach, wir gehen genau den umgekehrten Weg. Wir tun einfach so, als würden wir den Gegenstand wieder aus dem Rucksack nehmen und schauen, ob wir ein korrektes Ergebnis bekommen.\\
Fangen wir beim 1. Gegenstand an. Wir sind noch immer ganz links unten, bei results[0][30]. Wenn wir jetzt den Gegenstand rausnehmen, bekommen wir wieder 5 an freien Volumen dazu. Ziehen wir von unserem belegten Volumen 5 ab, landen wir in der Zeile mit dem Index 25 (30 - 5 = 25). Schauen wir nun zum nächsten Gegenstand, der sich in der nächsten Spalte (results[1][25]) befindet, sehen wir dort den Wert 30. Was bedeutet dieser Wert? Das ist der Wert in unserem Rucksack ohne den 1. Gegenstand (38 - 8 = 30). An dieser Stelle steht wiederum das Maximum für das aktuelle Volumen und den aktuellen Gegenstand. Da die Rückrechnung korrekt ist, haben wir unseren Gegenstand in der Rekursion zuvor ausgewählt.\\
Wir haben den 1. Gegenstand zurückgerechnet und sind beim Index [1][25]. Versuchen wir das gleiche nochmal für den 2. Gegenstand, der ebenfalls das Volumen 5 und den Wert 8 hat. Nehmen wir den 2. Gegenstand ebenfalls wieder raus, landen wir bei results[2][20], wo wir den Wert 20 finden. Dieses Ergebnis passt aber nicht. Wenn wir von unserem aktuellen Wert im Rucksack 8 abziehen, bekommen wir 22 (30 - 8) und nicht die angegebenen 20. Dieser Gegenstand war also nicht im Rucksack. Wie gehts jetzt weiter? Wir bleiben in unserer Zeile 25 und gehen einfach zum nächsten Gegenstand (in die nächste Spalte). In results[2][25] haben wir wieder den Wert 30. Das passt, denn wir hatten den Gegenstand nicht im Rucksack, also hat sich der Wert auch nicht verändert. Die Rechnung ohne den 2. Gegenstand ist wiederum korrekt.\\
Wenn man dieses Schema für alle Gegenstände weiterführt, kommt man zu den gesuchten Gegenständen. Diese Art der Rückrechnung nennt man "Backtracking".\\
Nochmal zusammenfassend die Schritte:
- Rekursion durchführen.
- Maximalen Wert in Spalte 0 suchen, sollte mit dem Ergebnis der Rekursion übereinstimmen.
- Volumen des aktuellen Gegenstands vom belegten Gegenstand abziehen. Ist der Wert im Rucksack korrekt?
- Ist die Rechnung korrekt, war der Gegenstand im Rucksack. Volumen abziehen und zum nächsten Gegenstand.
- Ist die Rechnung nicht korrekt, bleibt das Volumen gleich und man geht einfach zum nächsten Gegenstand.
- Schritt 3 für alle Gegenstände wiederholen.
Unser Rechenweg durch die Dynamisierungs-Matrix sieht folgendermaßen aus:
| ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^
^ 0 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 |
^ 1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 2 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 3 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 |
^ 4 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 5 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 |
^ 6 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 |
^ 7 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 8 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 |
^ 9 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 10 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
^ 11 | -1 | -1 | -1 | -1 | 10 | 5 | 0 | 0 | 0 | 0 |
^ 12 | -1 | -1 | -1 | -1 | 10 | 10 | 10 | 0 | 0 | 0 |
^ 13 | -1 | -1 | -1 | -1 | -1 | -1 | 10 | 0 | 0 | 0 |
^ 14 | -1 | -1 | -1 | 10 | 10 | 10 | 10 | 0 | 0 | 0 |
^ 15 | -1 | -1 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 0 |
^ 16 | -1 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 17 | -1 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 18 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 20 | 20 | 0 |
^ 19 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 20 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 21 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 22 | -1 | -1 | -1 | -1 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 23 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 24 | -1 | -1 | -1 | 25 | 20 | 20 | 20 | 20 | 20 | 0 |
^ 25 | -1 | 30 | 30 | 30 | 30 | 20 | 20 | 20 | 20 | 0 |
^ 26 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 27 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 28 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 29 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
^ 30 | 38 | 38 | 37 | 37 | 37 | 37 | 37 | 37 | 20 | 20 |
Bei der optimalen Lösung werden also die Gegenstände 1, 5 und 9 ausgewählt. Eine mögliche Implementierung könnte so aussehen:
// g++ knapsack_selection.cpp
#include
#include
#include
// currentVolume: Das restliche (freie) Volumen im Rucksack
// i: Aktueller Gegenstand
// Return value: Maximaler Wert mit bzw. ohne den aktuellen Gegenstand
int knapsack( const int currentVolume, const int i );
// Maximale Anazahl an Gegenständen
const int maxN = 10;
// Maximales Volumen des Rucksacks
const int maxV = 30;
// Anzahl an Byte für unseren Dynamisierungs-Array
const int resultLength = ( maxV + 1 ) * sizeof( int );
// Volumen des Rucksacks
int V;
// Anzahl an Gegenständen
int n;
// Volumen der einzelnen Gegenstände
int v[maxN];
// Werte der einzelnen Gegenstände
int w[maxN];
// Gespeicherte Ergebnisse von bisherigen Berechnungen
int results[maxN][maxV + 1];
int main()
{
// Eingabe der Daten
scanf( "%d %d", &V, &n );
for( int i = 0; i < n; i++ )
scanf( "%d %d", &( v[i] ), &( w[i] ) );
// Initialisierung der Dynamisierungs-Matrix mit -1
for( int i = 0; i < n; i++ )
memset( results[i], -1, resultLength );
// Berechnung des optimalen Wertes
int r = knapsack( V, 0 );
// Belegtes Volumen beim optimalen Ergebnis suchen.
// Das optimale Ergebnis befindet sich immer in der ersten Spalte!
int currentVolume = -1;
for( int i = 0; i <= maxV && currentVolume == -1; i++ )
{
if( results[0][i] == r )
currentVolume = i;
}
// Über alle Gegenstände iterieren (-1, weil mit i+1 gerechnet wird)
for( int i = 0; i < n - 1; i++ )
{
// Zuerst prüfen ob der aktuelle Gegenstand überhaupt in den Rucksack passt, dann
// versuchen den aktuellen Gegenstand aus dem Rucksack zu nehmen.
// Stimmt der Wert an der neuen Position?
// aktueller Wert im Rucksack - Wert des aktuellen Gegenstands
// == Maximum für diesen Gegenstand mit dem neuen Volumen
if( currentVolume - v[i] >= 0
&& r - w[i] == results[i + 1][currentVolume - v[i]] )
{
// Gegenstand war im Rucksack
printf( "selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
// Restlichen Wert im Rucksack anpassen
r -= w[i];
// Restliches Volumen der Gegenstände im Rucksack anpassen
currentVolume -= v[i];
}
else
{
// Gegenstand war nicht im Rucksack
printf( "NOT selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
}
}
// Der letzte Gegenstand muss speziell geprüft werden, da der Index
// i + 1 dann nicht mehr vorhanden ist.
// Ist jetzt noch etwas im Rucksack, muss es der letzte Gegenstand sein.
// r entspricht damit auch dem Wert des letzten Gegenstandes
if( r > 0 )
printf( "selecting %d (%d / %d)\n", n, v[n - 1], w[n - 1] );
else
printf( "NOT selecting %d (%d / %d)\n", n, v[n - 1], w[n - 1] );
return 0;
}
int knapsack( const int currentVolume, const int i )
{
if( i < n )
{
if( results[i][currentVolume] != -1 )
return results[i][currentVolume];
return results[i][currentVolume] = std::max( knapsack( currentVolume, i + 1 ),
( currentVolume - v[i] >= 0 )
? ( w[i] + knapsack( currentVolume - v[i], i + 1 ) )
: 0 );
}
return 0;
}
Ausgabe:
selecting 1 (5 / 8)
NOT selecting 2 (5 / 8)
NOT selecting 3 (6 / 6)
NOT selecting 4 (8 / 5)
selecting 5 (10 / 10)
NOT selecting 6 (11 / 5)
NOT selecting 7 (12 / 10)
NOT selecting 8 (15 / 17)
selecting 9 (15 / 20)
NOT selecting 10 (30 / 20)
===== Abschließendes =====
Knapsack ist nicht umsonst ein so beliebtes Beispiel in der Algorithmik. Man kann daran einige wichtige Lektionen zur effizienten Implementierung eines Algorithmus erlernen. Viele andere Probleme basieren darauf, auch wenn das auf den ersten Blick nicht offensichtlich ist.\\
Rekursion ist eines der grundlegenden Mitteln der Programmierung. Auch wenn sie Anfängern oft Schwierigkeiten bereitet, lohnt es sich auf jeden Fall sich genau damit auseinanderzusetzen. Dynamische Programmierung hilft dabei den Performance-Nachteil gegenüber einer iterativen Lösung zu minimieren. Wie immer gilt: Übung macht den Meister!
===== Siehe auch =====
* [[http://www.proggen.org/forum/viewtopic.php?f=39&t=4927|Autorendiskussion]]
* [[http://www.proggen.org/forum/viewtopic.php?f=49&t=4970|Diskussion Backtracking]]
* [[http://www.proggen.org/forum/viewtopic.php?f=39&t=5752|Diskussion alternativer Backtracking-Algorithmus]]
* [[algo:prefix-sum:start|Präfixsumme]]