Das Subset-Sum Problem

Definition:
Ein Knapsack-Vektor (knapsack - dt. Rucksack) ist eine Menge von positiven, paarweise verschiedenen ganzen Zahlen:

A = (a1, a2, ..., an), ai != aj für i != j

Definition:
Unter dem allgemeinen Subset-Sum Problem wird folgendes verstanden:

Gegeben:
Ein Knapsack-Vektor A = (a1, a2, ..., an) sowie eine positive ganze Zahl s, Summe genannt.
Frage:
Gibt es eine Teilmenge A' von A mit SUMa' aus A'(a') = s, oder äquivalent:
Gibt es einen Vektor X = (x1, x2, ..., xn), xi aus {0, 1}, so dass AX = s?

Hier und im Folgenden ist AX = a1x1 + a2x2 + ... + anxn.

Das gerade beschriebene Subset-Sum Problem ist ein Entscheidungsproblem. Das entsprechende Berechnungsproblem lautet, denjenigen Vektor X = (x1, x2, ..., xn), xi aus {0, 1}, zu finden, so dass AX = s.
Das mit dem Knapsack-Vektor A und der Summe s verbundene Berechnungsproblem wird im Folgenden mit (A, s) bezeichnet.

Beispiel:
Seien A = (15, 22, 14, 26, 32, 9, 16, 8) und s = 53 gegeben. Eine Lösung für (A, 53) ist X = (1, 1, 0, 0, 0, 0, 1, 0), da AX = a1 + a2 + a7 = 15 + 22 + 16 = 53. Die entsprechende Teilmenge ist A' = (15, 22, 16).
Die Lösung muss jedoch nicht eindeuting sein; so ist X = (0, 1, 1, 0, 0, 1, 0, 1) ist eine weitere Lösung für (A, 53).

Es ist kein kein Algorithmus bekannt, der das allgemeine Subset-Sum Problem effizient löst. In der Tat ist das Entscheidungsproblem ein NP-vollständiges, das Berechnungsproblem ein NP-hartes Problem. Hinsichtlich der Berechenbarkeit sind beide äquivalent: gibt es einen Algorithmus, der das Entscheidungsproblem effizient löst, so kann dieser Algorithmus zum Berechnen des Lösungsvektors herangezogen werden und umgekehrt.

Eine Methode, für gegebenen Knapsack-Vektor A und eine Summe s einen möglichen Lösungsvektor X zu finden, ist die naive Methode: für jeden Vektor X = (x1, ..., xn), xi = {0, 1}, wird s' = AX berechnet. Falls s' = s, ist X die gesuchte Lösung.
Dieser Algorithmus testet im schlechtesten Fall alle 2n verschiedene Vektoren X, daher hat dieser Algorithmus eine Laufzeit von O(2n).

Einer der besten Algorithmen für das allgemeine Subset-Sum Problem ist der Meet-in-the-middle Algorithmus. Dieser teilt den ursprünglichen Knapsack-Vektor A in zwei etwa gleich große Hälften A1 = (a1, ..., at) und A2 = (at+1, ..., an) auf und ermittelt in einer Vorberechnung alle möglichen Summen s1 = A1X1. Dabei ist t = n/2, falls n gerade, sonst ist t = (n-1)/2. Diese Summen werden zusammen mit den entsprechenden X-Vektoren in einer Tabelle, sortiert nach der Summe, abgespeichert.
Im zweiten Schritt wird dann für jeden möglichen Vektor X2 die Summe s2 = A2X2 ermittelt und nachgesehen, ob die Differenz L = s - s2 in der Tabelle enthalten ist. Dann gilt nämlich, L = s - s2 oder s = L + s2 = s1 + s2 = A1X1 + A2X2. Den Lösungsvektor X erhält man durch Aneinanderhängen von X1 und X2: X = X1||X2.

Eingabe: ein Knapsack-Vektor A = (a1, ..., an) und eine Summe s.
Ausgabe: Ein Vektor X = (x1, ..., xn), xi aus {0, 1}, mit AX = s, sofern eine Lösung existiert.

  1. Teile A auf in A1 = (a1, ..., at) und A2 = (at+1, ..., an).
    Für jeden möglichen Vektor X1 = (x1, ..., xt):
    • berechne s1 = A1X1
    • speichere s1 zusammen mit dem entsprechenden Vektor X1 in einer Tabelle T ab
    • sortiere T nach der Summe s1
  2. Für jeden möglichen Vektor X2 = (xt+1, ..., xn):
    • berechne s2 = A2X2.
    • bilde die Differenz L = s - s2
    • überprüfe, ob T einen Eintrag enthält, der als erste Komponente den Wert L hat. Falls solch ein Eintrag in T existiert, ist X = X1||X2 eine Lösung.
Im ersten Schritt werden alle 2n/2 verschiedenen Summen s1 berechnet. Das Sortieren einer Menge mit t Elementen kann in O(t log(t)) Schritten getan werden. Bei 2n/2 Elementen beträgt die Laufzeit also O((n/2)2n/2).
Der zweite Schritt ermittelt im schlechtesten Fall alle 2n/2 verschiedenen Summen s2. Das Suchen eines Elementes in einer sortierten Menge mit t Elementen geschieht in Zeit O(log(t)). Im schlechtesten Fall müssen alle 2n/2 Summen gesucht werden, deshalb ist die Laufzeit von Schritt zwei O((n/2)2n/2).
Zusammen ergibt sich eine Laufzeit von O(n2n/2). Zusätzlich benötigt der Algorithmus O(2n/2) Speicherplatz für die Tabelle.

Applet starten

 
Superansteigende Knapsacks