Weiß jemand, wie dynamische Programmierung geht, oder hat eine gute Erklärung dafür?
Ich hab mir dazu den Wikipedia-Artikel angeschaut (Deutsch und Englisch), aber ich verstehe die Gemeinsamkeiten der Algorithmen ehrlich gesagt nicht.
Kann zum Beispiel jemand Rucksackproblem – Wikipedia erklären?
Wie kann man bestimmen, welcher Algorithmus zur dynamischen Programmierung gehört und welcher nicht?
Dynamische Programmierung ist, wenn du die Lösung eines Problems einer gewissen Größe aus den Lösungen kleineren Umfangs ableiten kannst. Ganz einfaches Beispiel wäre die Fibonacci-Folge: Dynamic programming and the Fibonacci series - Damavis Blog
Das funktioniert aber nicht für alle Arten von Problemen: Es kann sein, dass es überhaupt keine sinnvolle Aufteilung in Teilprobleme gibt, oder es gibt „Sprünge“ im Verhalten, die keinen Schluss von kleineren auf größere Probleme zulassen. Und dann kann es noch sein, dass dynamische Programmierung „prinzipiell“ funktioniert, aber die Anzahl der benötigten Teillösungen so stark wächst, dass es praktisch nicht anwendbar ist.
Danke sehr. Bin schon schlauer …
Zeile 6 ( R[i,j] := max( v(i) + R[i+1, j-w(i)], R[i+1,j] ) ) verstehe ich noch nicht richtig …
v == value und w == weight … das ist klar. Aber wieso kann auf den (i+1). Wert der Matrix/Tabelle zugegriffen werden, wenn der (i). Wert gerade erst gesetzt werden soll? Das will noch nicht in meinen Kopf hinein …
Könnte jemand diese Zeile erklären? Das scheint „die Magie“ des Rucksackproblems zu sein.
Schau dir doch einfach mal ein Video, wo das jemand von Hand macht, etwa dieser junge Herr: https://www.youtube.com/watch?v=8LusJS5-AGo
Am Anfang etwas konfus, und sollte man besser mit Untertiteln schauen, aber man sieht dann schön, wie in jeder Spalte das Gewicht um 1 hochgeht, und in jeder Zeile ein neues Item berücksichtigt wird. Dabei wird immer „zurückgeschaut“, nach dem Motto: Falls ich das neue Item nehme, habe ich noch soundsoviel kg Gewicht übrig, das ich optimal mit den schon bekannten Teilen füllen kann - und da schaut er immer rückwärts zu den schon berechneten Werten (genau das macht den Algorithmus „dynamisch“). Das neue Teil muss man aber nicht nehmen, es kann auch sein dass die alte Lösung mit den vorhandenen Items besser war.
Ich weiß jetzt nicht, ob das 100% dem Wikipedia-Algorithmus entspricht, aber es geht ja erst mal ums Prinzip, was eigentlich abgeht, und da macht Wikipedia hier keinen besonders guten Job.
Dynamische Programmierung ist wirklich nichts „magisches“, es ist gesunder Menschenverstand: Ich will meinen Rucksack füllen. Hilft es mir, wenn ich für 10kg Platz habe, wenn ich die optimalen Lösungen für 1…9kg schon kenne? Ja. Hilft es mir, wenn ich fünf Teile habe, wenn ich schon alle optimalen Lösungen für die ersten vier Teile kenne? Ja. Also schreibe ich alles hübsch geordnet auf, und gehe dann systematisch von kleineren zu größeren Lösungen.
Was den Algorithmus ein wenig komplizierter macht ist, dass es nicht nur um eine Dimension wie bei der Fibonacci-Folge geht, sondern zwei (Gewicht und Teile).
Arr, verstanden. 
Zwei wichtige Sachen: Die for-Schleife läuft rückwärts (FOR i = n … 1) bei Wikipedia (also wäre der (i+1). Index genau genommen der (i-1). Index 
) und die Matrix R wird mit default values (0) vorinitialisiert.
Das steht bei Wikipedia nicht direkt bei dem Pseudocode, aber als ein Kommentar in der C++-Implementierung.
Ok, wieder etwas gelernt.