TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 32

Nachdem es hier einige Probleme gab, habe ich eine mögliche (und hoffentlich richtige) Lösung eingetragen.

Gefragt ist eine Lösung für das 0/1-Rucksackproblem mit 5 Gegenständen in einer (n+1) x (K+1) - Matrix.

Lösungsvorschlag

In der Angabe gibt es weiters die Angabe, dass das Feld $m_{i,j}=max\{m_{i-1,j-w_{i}}+c_{i},m_{i-1,j}\}$ ist. Das Problem an dieser Formel ist, dass es einige Lösungen gibt, die aus der Matrix rausführen, sprich eine ungültige Lösung liefern. In diesem Fall habe ich den ganzen Ausdruck einfach auf "undef" gesetzt.

Zu verstehen sind die Zeilen folgendermaßen: In der 1. Zeile stehen alle Möglichkeiten, den 1. Gegenstand mitzunehmen oder dazulassen. Wenn ich ihn mitnehme habe ich Gewicht 4 und Kosten 4: In $m_{1,4}$ wird 4 eingetragen. Entsprechend wird, wenn ich ihn dalasse in $m_{1,0}$ 0 eingetragen.

In der 2. Zeile sind alle Kombinationen des 2. Gegenstandes mit der ersten Zeile, sprich 4 Lösungen. Binär ausgedrückt: 00 (keinen der beiden),01 (nur den 2. Gegenstand),10 (nur den 1. Gegenstand),11 (beide Gegenstände). Die Ergebnisse der Kosten: 00=>0, 01=>6, 10=>4, 11=>10. Die Gewichte der Ergebnisse: 00=>0, 01=>4, 10=>4, 11=>10. Man sieht daher sofort, dass es bei gleichem Gewicht (=4) zwei Lösungen gibt, die unterschiedliche Kosten haben. Daher wählt man die bessere und ersetzt den vorigen Wert dadurch.

Grundsätzlich wird jede Zeile zunächst von der vorangegangenen Zeile kopiert. Dann werden die Kombinationen durchgespielt und gegebenfalls der Wert ersetzt (ähnlich wie beim Dijkstra-Algorithmus).

Entsprechend müsste dann die Matrix folgendermaßen aussehen:

i/j	0	1	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0
1	0	/	/	4	/	/	/	/	/	/
2	0	/	/	6	/	/	/	10	/	/
3	0	/	/	6	/	/	/	10	10	/
4	0	/	6	6	5	6	12	10	10	/
5	0	/	6	6	8	6	12	14	14	/

Siehe auch die Diskussion im Informatik-Forum: Informatik-Forum Thread