Hallo
Iomegan hat geschrieben:Es gibt hier diese schöne Beschreibung des Rucksackproblems:
http://www.proggen.org/doku.php?id=algo:knapsack
Der dynamische Algorithmus macht was er soll und ich habe die Theorie weitestgehend verstanden, auch wenn ich manchmal noch stark nachdenken muss
Schön, dass dir mein Artikel gefällt
Falls es Kritik positiver oder negativer Art gibt, nur her damit
Iomegan hat geschrieben:Mein Problem ist, dass ich nicht nur wissen möchte was am Ende der größte Wert ist, sondern auch welche Gegenstände genau nun im Rucksack sind. Müsste doch eigentlich recht einfach sein rauszufinden wessen Werte letztendlich zusammen addiert worden sind.
Ich hab schon einiges hin und her probiert, finde aber keine Lösung.
Die Lösung dafür ist recht kompliziert und nicht grade offensichtlich. Leider bin ich noch nicht dazu gekommen das in den Artikel einzubaun.
Hier die Erklärung (ich werde das bei Gelegenheit ins Wiki übertragen):
Vorweg: Dein gesuchtes Ergebnis ist 1, 5 und 9. Die Gegenstände mit diesen Nummern werden verwendet.
An diesem Punkt solltest du dir ganz bewusst werden was deine Dynamisierungsmatrix (results[][]) überhaupt ist. Sie speichert den maximalen Wert im Rucksack an einem bestimmten Index und Volumen. Sehen wir uns deine Dynamisierungsmatrix an (ich hab sie etwas kleiner gemacht: maxN = 10, maxV = 30). Dafür hab ich folgenden Code, den du einfach nach dem Aufruf deiner Rekursion in main einfügen kannst:
Code: Alles auswählen
fprintf( stdout, " " );
for( int i = 0; i < maxN; i++ )
fprintf( stdout, "%2d ", i );
fprintf( stdout, "\n" );
for( int i = 0; i < maxV + 1; i++ )
{
fprintf( stdout, "%2d ", i );
for( int j = 0; j < maxN; j++ )
fprintf( stdout, "%2d ", results[j][i] );
fprintf( stdout, "\n" );
}
Ausgabe:
Code: Alles auswählen
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
(Das wird im Forum nicht schön dargestellt, wenn es dich stört kopier es einfach in einen Texteditor)
Spalten sind Gegenstände, Zeilen die jeweiligen (belegte) Volumen. Die erste Spalte ist der Volumen-Index, die erste Zeile der Gegenstands-Index.
Wenn du genau darüber nachdenkst, kommst du auf folgendes: Dein maximaler Wert im Rucksack steht immer ganz links unten, in results[0][maxV] (Füllst du den Rucksack nicht komplett, musst du nach dem Index anstelle von maxV suchen, an dem results[0] maximal ist.). Warum? Weil dieser Wert als letztes berechnet wird. 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 results[0][maxV] ganz zum Schluss. Da du in allen Rekursionen davor immer das Maximum genommen hast, erhältst du hier das größte Maximum aller möglichen Rekursionswege (Anmerkung: In results[1][maxV] 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.).
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. Schauen wir nun in die nächste Spalte (results[1][25]), 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. Das 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 du dieses Schema für alle Gegenstände weiterführst, kommst du zu den gesuchten Gegenständen.
Da das etwas viel war, nochmal zusammenfassend:
1) Rekursion durchführen.
2) Maximalen Wert in Spalte 0 suchen, sollte mit dem Ergebnis der Rekursion übereinstimmen.
3) Volumen des aktuellen Gegenstands vom belegten Gegenstand abziehen. Ist der Wert im Rucksack korrekt?
3.1) Ist die Rechnung korrekt, war der Gegenstand im Rucksack. Volumen abziehen und zum nächsten Gegenstand.
3.2) Ist die Rechnung nicht korrekt, bleibt das Volumen gleich und man geht einfach zum nächsten Gegenstand.
4) Schritt 3 für alle Gegenstände wiederholen.
Eine Implementierung könnte so aussehen (Es wird der Einfachheit halber angenommen, dass der Rucksack komplett gefüllt wurde):
Code: Alles auswählen
int r = knapsack( V, 0 );
// Rucksack ist komplett gefüllt -> belegtes Volumen ist das maximale Volumen
int currentVolume = maxV;
// Über alle Gegenstände iterieren (-1, weil mit i+1 gerechnet wird)
for( int i = 0; i < maxN - 1; i++ )
{
// 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( r - w[i] == results[i + 1][currentVolume - v[i]] )
{
fprintf( stdout, "selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
r -= w[i];
}
else
fprintf( stdout, "NOT selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
}
Ausgabe:
Code: Alles auswählen
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)
Probe: 8 + 10 + 20 = 38 == Ergebnis der Rekursion
Ich hoffe ich habe dich nicht zu sehr verwirrt, aber das war die Antwort auf deine Frage
Sollte es Fragen geben, nur her damit
Versuch das jetzt seit heute morgen.