Rucksackproblem bei der Schatzsuche

Die Lernenden sollen sich in dieser Unterrichtseinheit mit dem Rucksackproblem auseinandersetzen. Dabei sollen sie einerseits die allgemeine Problemstellung kennen lernen, andererseits aber auch Lösungsalgorithmen entwickeln. Dazu werden verschiedene Versionen des Rucksackproblems, welche sich durch unterschiedliche Einschränkungen auszeichnen, betrachtet. Die Lernenden sollen für jede Version einen Lösungsalgorithmus finden/kennenlernen. Dabei sollen sie einerseits sehen, dass leichte Veränderungen der Problemstellung dazu führen können, dass ein Lösungsalgorithmus nicht mehr funktioniert, andererseits aber auch feststellen, dass äusserst komplexe Probleme sehr einfach sein können, wenn man bestimmte Einschränkungen macht. Lernziele

• Die Lernenden wissen, was das sogenannte Rucksackproblem ist.
• Die Lernenden können Algorithmen in Worten allgemein formulieren.
• Die Lernenden sehen, dass Lösungsalgorithmen oft nur für bestimmte Spezialfälle effizient sind.
• Die Lernenden verstehen, dass eine leichte Veränderung der Problemstellung zu grossen Änderungen bezüglich der möglichen Lösungsalgorithmen führen kann.
• Die Lernenden wissen, dass es Probleme gibt, welche algorithmisch nicht effizient lösbar sind.
• Die Lernenden können mit Hilfe von dynamischer Programmierung (von Hand) ein gegebenes Rucksackproblem lösen.
• Die Lernenden erkennen, das das Rucksackproblem auch mit Hilfe der dynamischen Programmierung nicht effizient lösbar ist.