Dynamische Programmierung anhand des Rucksackproblems

Dieses Unterrichtsmaterial soll in ca. 4 Lektionen Unterstützung bieten, um

• das Rucksackproblem in seinen verschiedenen Varianten kennen zu lernen,
• den Bottom-Up-Ansatz des dynamischen Programmierens (Tabelle) kennen zu lernen und zu verstehen,
• den Bottom-Up-Ansatz auch auf andere Probleme übertragen zu können und kleinere Anpassungen im Algorithmus selber vornehmen zu können.

Die enthaltenen Aufgaben sind dazu gedacht, wesentliche Inhalte zu vertiefen oder zu entdecken. Sie sollten von den Schülerinnen und Schülern in Einzel- oder Gruppenarbeit gelöst werden. Ein schrittweises Vorgehen ist wünschenswert, jede Lösungsphase sollte einhergehen mit einer anschliessenden Besprechung. Dies gilt in besonderem Masse für die Aufgaben 4, 6 und 17. Da die Lerneinheit schon recht viel Selbststudium und eigenes Entdecken umfasst, sollten die Aufgaben von/mit der Lehrperson besprochen werden, und nicht einfach nur die Lösungen abgegeben werden.