Das Kefk Network Wiki befindet sich im Testbetrieb.

Rucksackproblem

Aus Kefk.

Wechseln zu: Navigation, Suche

Bild:Knapsack.svg Das Rucksackproblem (oft mit RUCKSACK, KNAPSACK bezeichnet) ist ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzenwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzenwert der ausgewählten Objekte maximiert werden.

Die Entscheidungsvariante des Rucksackproblems fragt, ob ein zusätzlich vorgegebener Nutzenwert erreicht werden kann. Sie gehört zur Liste der 21 klassischen NP-vollständigen Probleme von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.

In der Kryptographie wird häufig eine andere Entscheidungsvariante betrachtet. Dabei werden nur die Gewichte betrachtet und es wird gefragt, ob es eine Teilmenge der Objekte gibt, die einen vorgebenen Gewichtswert genau erreicht. Diese Problemvariante wird auch als SUBSET-SUM bezeichnet. Basierend auf dieser Variante wurde das Public-Key-Kryptoverfahren Merkle-Hellman-Kryptosystem entwickelt, das sich allerdings als nicht besonders sicher herausstellte.

Inhaltsverzeichnis

Anschauung

Das Rucksackproblem hat seinen Namen aus folgender Anschauung heraus erhalten: Es sind verschiedene Gegenstände mit einem bestimmten Gewicht und einem Nutzenwert gegeben. Aus diesen Gegenständen soll nun eine Auswahl getroffen werden, die in einen Rucksack mit einer vorgegebenen Gewichtsschranke mitgenommen werden können. In der Literatur wird zur Veranschaulichung auch gerne der Dieb herangezogen, der nur einen kleinen Teil der Beute im Rucksack abtransportieren kann und nun versucht, das Maximum an Nutzwert herauszuschlagen.

Mathematische Formulierung

Gegeben sind eine endliche Menge von Objekten U. Durch eine Gewichtsfunktion w und der Nutzenfunktion v wird den Objekten ein Gewicht und ein Nutzenwert zugeordnet:

w:U\rightarrow\mathbb{R}
v:U\rightarrow\mathbb{R}

Des Weiteren gibt es eine vorgegebene Gewichtsschranke B \in\mathbb{R}.

Gesucht ist eine Teilmenge K\subseteq U, die die Bedingung

\sum_{u\in K} w(u) \le B einhält und die Zielfunktion \sum_{u\in K} v(u) maximiert.

Lösung mittels dynamischer Programmierung

Sind Gewichte und Nutzen ganzzahlig, so lässt sich der optimale Wert des Rucksackproblems auch mittels dynamischer Programmierung lösen. Seien dazu 1,\ldots,n die Elemente von U. 

Eingabe: U, B, w, v wie oben beschrieben
 R := (n+1) x 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)

Die Korrektheit folgt aus folgender Beobachtung:

Sei K * eine optimale Lösung. Dann ist K^*\backslash\{i\} eine optimale Lösung für die Instanz U\backslash\{i\} mit Maximalgewicht B − w(i). Es ist sofort klar, dass der Algorithmus O(n\cdot B) Schritte benötigt. Hierbei ist zu beachten, dass B eine zu seiner Eingabelänge exponentiell wachsende Größe ist.

Anwendungen

Viele reale Fragestellungen lassen sich auf dieses Problem bzw. den Lösungsansatz zurückführen. Oft steht eine begrenzte Kapazität zur Verfügung, welche nicht die gesamte Nachfrage befriedigen kann. Man denke z. B. an einen Lkw, der viele verschiedene Güter – mit einem bestimmten Gewinn – transportieren soll, aber wegen der begrenzten Lademenge nicht alle Güter aufnehmen kann. Der Besitzer des Lkws wird die Ladung so wählen, dass der Gewinn maximal ausfällt.

Weblinks

Von „http://www.kefk.org/wiki/Rucksackproblem“
Persönliche Werkzeuge