dynamische Programmierung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Zusammen,
Ich versuche gerade den dynamischen Lösungsansatz für das 0/1-Rucksack-Problem zu begreifen. Ich lese da z.B. Folgendes:
Developing a DP Algorithm for Knapsack:
Step 2: Recursively define the value of an optimal solution in terms of solutions to smaller problems.
Initial Settings: Set
[mm]\begin{array}{lll}
\textcolor{red}{V[0,w]:=0}&\texttt{for }\textcolor{blue}{0\leqslant w\leqslant W},&\texttt{no item}\\
V[i,w] := -\infty&\texttt{for }w< 0,&\texttt{illegal}
\end{array}[/mm]
Recursive Step: Use
[mm]\textcolor{red}{V[i,w]:=\max\left\{V[i-1,w],v_i+V\left[i-1,w-w_i\right]\right\}}[/mm] for [mm]\textcolor{blue}{1\leqslant i\leqslant n,\ 0\leqslant w\leqslant W}[/mm].
Die Anfangsbedingungen leuchten sofort ein (ein leerer Rucksack ist nichts Wert  ). Schwieriger wird es schon bei der rekursiven Definition. Wie kann man sich das informell vorstellen? Ich schreibe jetzt mal, was ich so bisher nachvollziehen konnte:
Wir haben unseren Rucksack bisher also optimal mit den Gegenständen [mm] $1,\dotsc,i-1$ [/mm] gefüllt, und der Rucksack wiegt $w$. Jetzt wollen wir noch einen Gegenstand reintun. Jetzt kann zweierlei passieren:
(1) Der Rucksack droht zu reisen. -> Die vorige Rucksack-Belegung mit $i-1$ Gegenständen beim gleichen(!?) Gewicht $w$ ist optimal.
(2) Der Rucksack droht nicht zu reisen. -> Dann hat unser Rucksack an Wert [mm] $v_i$ [/mm] des [mm]i\texttt{-ten}[/mm] Gegenstandes zugelegt. Der Rucksack ist aber auch schwerer geworden. Was bedeutet dann [mm] $w-w_i$?
[/mm]
Danke!
Viele Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:12 So 02.10.2005 | | Autor: | Frank05 |
> Die Anfangsbedingungen leuchten sofort ein (ein leerer
> Rucksack ist nichts Wert ). Schwieriger wird es schon
> bei der rekursiven Definition. Wie kann man sich das
> informell vorstellen? Ich schreibe jetzt mal, was ich so
> bisher nachvollziehen konnte:
>
> Wir haben unseren Rucksack bisher also optimal mit den
> Gegenständen [mm]1,\dotsc,i-1[/mm] gefüllt, und der Rucksack wiegt
> [mm]w[/mm].
Wichtig ist auch, dass du dir klar machst, dass der Rucksack zu diesem Zeitpunkt nicht unbedingt alle $i-1$ Gegenstaende beinhaltet, sondern nur eine Teilmenge dieser.
> Jetzt wollen wir noch einen Gegenstand reintun. Jetzt
> kann zweierlei passieren:
>
> (1) Der Rucksack droht zu reisen. -> Die vorige
> Rucksack-Belegung mit [mm]i-1[/mm] Gegenständen beim gleichen(!??)
> Gewicht [mm]w[/mm] ist optimal.
Wir bilden ein Maximum aus 2 Faellen. Diese beiden Faelle entsprechen anschaulich, ob wir nun den Gegenstand $i$ in den Rucksack packen oder eben nicht.
Fall 1 - Wir lassen den Gegenstand draussen:
$V[i-1,w]$ ist der optimale Zustand des Rucksacks bevor wir den Gegenstand $i$ betrachtet haben. Dabei gibt $w$ das Maximalgewicht an, das im Rucksack Platz hat. Da wir gegenueber der Betrachtung des Gegenstands $i-1$ nichts aendern kann dieser Wert unveraendern uebernommen werden. Der Wert der Gegenstaende ist gleich und auch das Maximalgewicht bleibt erhalten.
> (2) Der Rucksack droht nicht zu reisen. -> Dann hat unser
> Rucksack an Wert [mm]v_i[/mm] des [mm]i-\text{ten}[/mm] Gegenstandes
> zugelegt. Der Rucksack ist aber auch schwerer geworden. Was
> bedeutet dann [mm]w-w_i[/mm]?
Fall 2 - Gegenstand $i$ wird in den Rucksack gepackt:
[mm] $v_i [/mm] + [mm] V[i-1,w-w_i]$ [/mm] ist der neue Wert des Rucksacks bestehend aus [mm] $v_i$, [/mm] dem Wert des neuen Gegenstands $i$, und dem was sonst noch im Rucksack Platz hat. Hier ist der entscheidende Schritt des DPs. Wir haben uns jetzt entschieden, dass wir Gegenstand $i$ einpacken und nun verschieben wir das Problem auf ein kleineres Teilproblem. Wir bauen uns quasi einen neuen Rucksack. Dieser Rucksack hat nur noch [mm] $w-w_i$ [/mm] Kapazitaet und soll mit den Gegenstaenden $1 [mm] \dots [/mm] i-1$ optimal gefuellt werden. Den optimalen Wert fuer einen solchen Rucksack finden wir aber gerade in [mm] $V[i-1,w-w_i]$
[/mm]
Zum Schluss finden wir dann in $V[n,W]$ den Wert eines Rucksacks mit Maximalgewicht $W$, der optimal mit den Gegenstaende $1 [mm] \dots [/mm] n$ beladen ist.
Das schoene an den meisten DP Algorithmen ist, dass man sie auch einfach kurz implementieren kann, weil sie im Wesentlichen ja nur aus einer kleinen Rekursionsgleichung bestehen. Dementsprechend waere es vielleicht noch hilfreich, wenn du dir den Algorithmus mal implementierst und dir die fertig berechnete Tabelle mal fuer ein paar Beispiele ausgeben laesst und nachvollziehst. Einziger Fallstrick beim Implementieren sind die Tabellengrenzen, also das was in deiner Definition mit [mm] $-\infty$ [/mm] belegt wird, aber das bekommst du schon in den Griff
|
|
|
|
