Rucksackproblem

Das Rucksackproblem gehört zu den typischen Problemen eines Mathematikers, der seine lange Studienzeit für etwas sinnvolles nutzen will. Natürlich hat Mathematik keinerlei praktischen Nutzen, denn Mathe ist ja bekanntermaßen ein Arschloch.

Was ist das Rucksackproblem?

Das Rucksackproblem beschäftigt sich damit, in einen Rucksack eine Menge von Wertgegenständen zu packen, sodass der Rucksack später nicht überfüllt ist und den maximalen Wert erreicht...Klingonisch, ist auch so. Dabei gehört das Rucksackproblem zu den NP-vollständigen Problemen.

NP-Probleme sind warscheinlich nicht effizient, sondern in Polynomialzeit entscheidbare Probleme bzw. Algorithmen. Das bedeutet im Klartext, dass es totaler Schwachsinn ist, etwas berechnen zu wollen, da es zwei Ewigkeiten dauert und jeder normale Mensch mit einem Grundverständis der Mathematik die Lösung instinktiv finden kann. Doch Mathe wäre nicht Mathe wenn man als Mathematiker den Laien nicht mit abstrusen Konstruktionen das Maul stopfen könnte.

Szenario

Ein Mathematiker hat erfolgreich sein Studium abgeschlossen. Nach zwei Jahren Arbeitslosigkeit (Was will die Menschheit denn mit Mathematikern?) und einem Jahr an einer Schule als Mathematik- und Sportaushilfslehrer, hat der Guter keinen Bock mehr auf seine soziale Situation. Nach dem fünften Bier um drei Uhr mittags denkt er sich nun: "Ich hab ja studiert, also kann ich da bestimmt etwas von anwenden", und erinnert sich an das Rucksackproblem. Er entschließt sich dementsprechend Einbrecher zu werden, da er ja berechnen kann, wie er seinen Rucksack am besten mit dem Diebesgut beladen kann. Er scheitert zwar kläglich, hat aber immerhin ein neues Umfeld mit herzensguten Menschen im Knast... Anders als in der Schule.

Dabei gibt's aber folgende Probleme:

1. Zum Berechen braucht man sehr viel Zeit (NP-Problem), also muss man vorher sich auskennen und alles zu Hause berechnen, nochmals einbrechen und erst dann alles mitnehmen. Oder vor Ort die drei Wochen Berechnungszeit durchführen, aber wer kann schon solange ungesehen im Haus rumrennen?
2. Es wird vergessen, dass er ja noch Hände hat, indenen er einfach ja noch das eine oder andere nette mitgehn lassen kann. Was die Berechnung voll zunichte macht.
3. Man geht davon aus, dass alles schön stabelbar ist. Jaaa sichi.

Rechnung

Ist man dennoch wahnsinnig genug, das alles zu berechen, kann man folgenden Algorithmus verwenden:
U: Die Objekte der Begierde
B: Größe des Rucksacks (in kg, Litern, Scoville, Bier, nach der Richterskala, etc.)
w: Gewichtungsfunktion für die Objekte. Zum Beispiel w(Vulkan) = 600.000; w(Atombombe) = 2; in Tonnen
v: Wertfunktion der Objekte. v(Vulkan) = 5; v(Atombombe) = 1; in der Richterskala

   Eingabe: U, B, w, v

       R := [1…(n+1), 0…B]-Matrix, mit Einträgen 0

       FOR i = n … 1

           FOR j = 1 … B

               IF w(i) <= j

                   R[i,j] := max( v(i) + R[i+1, j-w(i)], R[i+1,j] )

               ELSE

                   R[i,j] := R[i+1,j]

   Ausgabe: R[1,B]