"Appelrath´s Knobeleien"
Das Weihnachtsrätsel
Lösung:
Hintergrund:
Intuitiv erscheint es sinnvoll, diejenigen Pakete zuerst auszuwählen, die den größten Wert pro Gewichtseinheit erzielen. Leider führt dieser Weg nicht immer zum optimalen Ergebnis.
Man kann allerdings, um die beste Lösung zu finden, alle möglichen Paketkombinationen für den Sack des Weihnachtsmanns ausprobieren („Brute-Force-Methode“). Für jedes Paket ist zu entscheiden, ob es in den Sack gepackt wird oder nicht. Pro Paket sind das zwei Möglichkeiten (im Sack oder nictht?). Bei acht Paketen ergeben sich insgesamt 28 = 256 Kombinationsmöglichkeiten, die überprüft werden müssen.
Dieser Ansatz funktioniert für das Beispiel gut, hat allerdings den Nachteil, dass die Anzahl der zu überprüfenden Kombinationen exponentiell "explodieren" würde, wenn noch mehr Pakete zur Auswahl stünden.
Das allgemeine Problem, aus einer Menge von Objekten (hier jeweils Geschenken mit Gewicht und Nutzwert) eine Teilmenge auszuwählen, die den Nutzwert der ausgewählten Objekte maximiert, wobei eine vorgegebene Gewichtsschranke nicht überschritten werden darf, wird als „Rucksackproblem“ bezeichnet. Für dieses klassische Problem der Informatik gibt es bis zum heutigen Tage keinen Lösungsweg (in der Informatik spricht man von „Algorithmus“), der auch für große Mengen von Objekten zu einem Ergebnis führt in akzeptabler Zeit, d.h. bei steigender Komplexität, d.h. zunehmender Zahl von Geschenken, einen mit einem Polynom wachsenden Zeitaufwand benötigt, um ein Ergebnis zu liefern. Da diese Problemklasse durchaus praxisrelevant ist, sind Algorithmen entwickelt worden, die das Problem näherungsweise lösen. So kann zum Beispiel mit Hilfe der Dynamischen Optimierung, einer Methode des Operations Research, das Rucksackproblem als ein mehrstufiges Entscheidungsproblem gelöst und dessen Komplexität reduziert werden.
Literatur:
Kellerer, Hans; Pferschy, Ulrich; Pisinger, David: Knapsack Problems. Springer, 2004, Martello, Silvano; Toth, Paolo: Knapsack problems: algorithms and computer implementations. J. Wiley, Chichester 1990
Links:
http://de.wikipedia.org/wiki/Rucksackproblem
http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php
Hintergrund:
Intuitiv erscheint es sinnvoll, diejenigen Pakete zuerst auszuwählen, die den größten Wert pro Gewichtseinheit erzielen. Leider führt dieser Weg nicht immer zum optimalen Ergebnis.
Man kann allerdings, um die beste Lösung zu finden, alle möglichen Paketkombinationen für den Sack des Weihnachtsmanns ausprobieren („Brute-Force-Methode“). Für jedes Paket ist zu entscheiden, ob es in den Sack gepackt wird oder nicht. Pro Paket sind das zwei Möglichkeiten (im Sack oder nictht?). Bei acht Paketen ergeben sich insgesamt 28 = 256 Kombinationsmöglichkeiten, die überprüft werden müssen.
Dieser Ansatz funktioniert für das Beispiel gut, hat allerdings den Nachteil, dass die Anzahl der zu überprüfenden Kombinationen exponentiell "explodieren" würde, wenn noch mehr Pakete zur Auswahl stünden.
Das allgemeine Problem, aus einer Menge von Objekten (hier jeweils Geschenken mit Gewicht und Nutzwert) eine Teilmenge auszuwählen, die den Nutzwert der ausgewählten Objekte maximiert, wobei eine vorgegebene Gewichtsschranke nicht überschritten werden darf, wird als „Rucksackproblem“ bezeichnet. Für dieses klassische Problem der Informatik gibt es bis zum heutigen Tage keinen Lösungsweg (in der Informatik spricht man von „Algorithmus“), der auch für große Mengen von Objekten zu einem Ergebnis führt in akzeptabler Zeit, d.h. bei steigender Komplexität, d.h. zunehmender Zahl von Geschenken, einen mit einem Polynom wachsenden Zeitaufwand benötigt, um ein Ergebnis zu liefern. Da diese Problemklasse durchaus praxisrelevant ist, sind Algorithmen entwickelt worden, die das Problem näherungsweise lösen. So kann zum Beispiel mit Hilfe der Dynamischen Optimierung, einer Methode des Operations Research, das Rucksackproblem als ein mehrstufiges Entscheidungsproblem gelöst und dessen Komplexität reduziert werden.
Literatur:
Kellerer, Hans; Pferschy, Ulrich; Pisinger, David: Knapsack Problems. Springer, 2004, Martello, Silvano; Toth, Paolo: Knapsack problems: algorithms and computer implementations. J. Wiley, Chichester 1990
Links:
http://de.wikipedia.org/wiki/Rucksackproblem
http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php
