4.5.2 Superincreasing knapsacks

Despite the assumption of being NP-hard there are special subset sum problems (A, s) efficiently and fast solvable.

Definition:
Let A = (a₁, ..., a_n) be a knapsack vector. Then A is called superincreasing, if a_i is greater than the sum of the preceding a_j:

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

For example the knapsack A = (1, 2, 4, 8, 16) is a superincreasing one.

The following algorithm solves the problem (A, s) provided that A is superincreasing:

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).

The presented algorithm linearly tests all components of A and hence the running time is O(n).

The following applet is initialized, so that a solution exists.
To get a superincreasing sequence with larger elements, input a value into the textfield a(1) and press the new knapsack button.
White textfiels mean, that user input is possible.

source

The basic Merkle-Hellman Cryptosystem

	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).