4.5.2 Superansteigende Knapsack-Vektoren

Obwohl das allgemeine Subset-Sum Problem NP-vollständig ist, gibt es spezielle Probleme (A, s), die schnell und einfach lösbar sind.

Definition:
Sei A = (a₁, ..., a_n) ein Knapsack-Vektor. A ist superansteigend (superincreasing), falls a_i größer ist als die Summe der vorhergehenden a_j:

a_i > a₁ + ... + a_i-1

Zum Beispiel ist der Knapsack-Vektor A = (1, 2, 4, 8, 16) superansteigend.

Der folgende Algorithmus löst ein Problem (A, s), wenn A = (a₁, a₂, ..., a_n) superansteigend ist:

for i := n downto 1

if s >= a_i then x_i := 1 and s := s - a_i
else x_i := 0

if s != 0 then return (no solution)
else return (x₁, x₂, ..., x_n).

Dieser Algorithmus durchläuft linear die einzelnen Elemente von A und hat daher eine Laufzeit von O(n).

Das Applet ist so initialisiert, dass eine Lösung existiert.
Durch Eingabe eines Wertes in das Feld a(1) und anschließendem Drücken des new knapsack-Buttons wird a(1) zur Erzeugung der superansteigenden Menge herangezogen.
Weiße Textfelder bedeuten, dass eine Eingabe möglich ist.

source

Merkle-Hellman Kryptosystem

	for i := n downto 1
	if s >= a_i then x_i := 1 and s := s - a_i else x_i := 0
	if s != 0 then return (no solution) else return (x₁, x₂, ..., x_n).