Knapsack Problem? O(2^n)?

Hi

Kann mir jemand intuitiv erklären, warum die Komplexität des Problems 2^n ist?

Answer 1

[Rammstein53]

Das Knapsack-Problem lässt sich rein mathematisch so beschreiben:

Es existieren Wertepaare (a_i,b_i), i = 1 ... n, a_i,b_i € R

Weiter sei

$y\ =\ \sum_{i\ =1}^nai\ \cdot\ xi$

und

$z\ =\ \sum_{i=1}^nbi\ \cdot\ xi$

Mit x_i = 0 oder x_i = 1 für i = 1 ...n.

Nun sucht man Extrempunkte von y unter der Bedingung z < G

Weil die x_i nur die Werte 0 oder 1 annehmen können, gibt es für deren Auswahl 2^n verschiedene Möglichkeiten (vergleichbar mit einer Binärzahl). Die Summen y und z sind dann lediglich eine Addition der entsprechenden a_i und b_i. Deshalb liegt die Komplexität des Problems bei 2^n.