In dieser Vorlesung betrachten wir weitere Dynamic Programming-Ansätze. Dabei geht es unter anderem um das bekannte Knapsack-Problem. Zudem betrachten wir zwei geometrische Probleme.

Folien: VL4.pdf ,VL4_no_animation.pdf
Video: [YouTube]

Weitere Links

Dynamic Programming by Richard Bellman, 1957 (Originalarbeit als PDF)
Finding a largest convex subset at Stack Overflow
On the Chromatic Art Gallery Problem (Forschungsartikel von 2014, gezeigt hatte ich das Bild auf Seite 5.)
A graphical introduction to Dynamic Programming (ganz nett gestaltet, erstes Beispiel ist die Berechnung der Fibonacci-Zahlen, also gut zugänglich)
Titelbild-XKCD