DIE CHALLENGE
Und? Gepackt?
Die optimale Packmethode erfordert etwas Kopfrechenleistung. Aus dem Gewicht und dem Nutzwert kann für jeden Gegenstand nämlich ein Quotient errechnet werden.
Nutzen : Gewicht = ?
Je größer der Quotient ist, desto nützlicher ist der Gegenstand pro Gramm. Ordnen wir also zuerst die Gegenstände nach ihrem Quotienten, von hoch bis niedrig. Sind zwei Quotienten gleich, sollte zuerst der Gegenstand mit dem größeren Gewicht ausgewählt werden. Das folgende Prinzip gilt:
| Passt der Gegenstand noch hinein? | ||
| JA: Den Gegenstand einpacken und das noch verfügbare Gewicht berechnen. | NEIN: Gibt es noch einen nächsten Gegenstand in der Reihe? | |
| JA: Zum nächsten Gegenstand übergehen, und wieder oben anfangen. | NEIN: Der Platz ist optimal ausgenutzt. | |
Das ist Informatik!
Auf der Suche nach einem Algorithmus kann das Problem zunächst mathematisiert werden:
Gegeben: a1, a2, ..., an (Gewichte) und w1, w2, ..., wn (Nutzwerte) sowie ein Grenzgewicht g.
Gesucht: x1, x2, ..., xn mit xk = 0 oder xk = 1 und x1 · a1 + x2 · a2 + ... + xn · an ≤ g und x1 · w1 + x2 · w2 + ... + xn · wn → max.
Die Ausgabe xk = 1 bedeutet, dass das Objekt eingepackt wird.
Die offensichtlichste Lösung ist, alle möglichen Kombinationen zu erzeugen und zu prüfen, ob das Maximalgewicht überschritten wurde. Die beste Kombination wird ausgewählt. Für größere Objektmengen ist dieser Algorithmus jedoch sehr zeitaufwendig und deshalb ungeeignet.
Einen polynomialen Algorithmus – der auf die Rechenzeit bezogen besonders effiziente Lösungen findet – gibt es bis heute nicht. Denn: Beim Rucksackproblem handelt es sich um ein NP-vollständiges Problem, also eines der schwierigsten Probleme der Informatik.
In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Als „NP-vollständig“ klassifizierte Probleme lassen sich vermutlich nicht effizient lösen. Das heißt, das die Lösung selbst relativ kleiner Probleme auf Rechnern viel Zeit in Anspruch nehmen würde. Für real auftretende Größenordnungen gibt es aber oft selbst für NP-vollständige Probleme Lösungsverfahren, anhand derer sie in akzeptabler Zeit lösbar sind.
Dazu:
Richard M. Karp: Reducibility Among Combinatorial Problems. In: R. E. Miller und J. W. Thatcher (Hrsg.): Complexity of Computer Computations. Plenum Press, New York, 1972, S. 85–103
In der Kryptografie betrachtet man häufig ein etwas anderes Zielkriterium. Dabei schaut man nur auf die Gewichte und fragt danach, ob es eine Teilmenge der Objekte gibt, die den vorgegebenen Gewichtswert genau erreicht. Dieses Rätsel kennt man unter dem eleganten Spitznamen Untermengensummenproblem.
Dazu:
Soma, Nei Y. Toth, Paolo: An exact algorithm for the subset sum problem. European Journal of Operational Research 136, S. 57–66.