Knapsack-Problem

Knapsack-Problem
Das Rucksackproblem: Welche der Gewichte können in den Rucksack mit Maximallast von 15 kg gepackt werden, so dass der Geldwert maximal wird? (Lösung in diesem Fall: Alle Gewichte außer dem schwersten einpacken.)

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

Die Entscheidungsvariante des Rucksackproblems fragt, ob ein zusätzlich vorgegebener Nutzwert 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 Nutzwert 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 die Nutzenfunktion v wird den Objekten ein Gewicht und ein Nutzwert 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 := [1…(n+1), 0…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]

In jeder Speicherzelle R(i,j) ist der maximale Nutzwert bei maximal möglichen Gesamtgewicht von j bei Berücksichtigung einer Teilmenge von Gegenständen aus der Teilsequenz [i..n] der Gesamtsequenz aller Gegenstände [1..n]. Also ist der maximale Nutzwert bei Berücksichtigung einer Teilmenge aller Gegenstände in der Zelle R(1,B) nach Beendigung des Algorithmus gespeichert.

In jeder Zeile i der Matrix R wird über die beiden Fälle optimiert, ob der Nutzwert maximal vergrößert werden kann, wenn der Gegenstand i mit dem Gewicht w(i) dem Rucksack hinzugefügt oder er nicht aufgenommen wird. Im ersten Fall erhöht sich der Nutzwert um v(i).

Um den Inhalt des Rucksacks mit dem maximalen Nutzwert zu bestimmen, kann er rekonstruiert werden, indem die Berechnung des Optimums in R(1,B) mittels Backtracking zurückverfolgt wird.

Die Korrektheit folgt aus folgender Beobachtung:

Sei K^\star eine optimale Lösung. Dann ist K^\star\backslash\{i\} eine optimale Lösung für die Instanz U\backslash\{i\} mit Maximalgewicht Bw(i). Der Algorithmus benötigt aufgrund der verschachtelten for-Schleifen, die über n und B iterieren, eine Laufzeit von O(n\cdot B). Hierbei ist zu beachten, dass B eine zu seiner Eingabelänge exponentiell wachsende Größe und somit die Laufzeit pseudopolynomiell 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 wollen, dass der Gewinn maximal ausfällt.

Literatur

  • Kellerer, Hans; Pferschy, Ulrich; Pisinger, David: Knapsack Problems. Springer, 2004, ISBN 978-3-540-40286-2. 
  • Martello, Silvano; Toth, Paolo: Knapsack problems: algorithms and computer implementations. J. Wiley, Chichester 1990, ISBN 978-0-471-92420-3 (Buch als PDF und Fortran-Quelltext zum Buch). 

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Knapsack problem — BKP redirects here. For other uses, see BKP (disambiguation). Example of a one dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to… …   Wikipedia

  • knapsack problem — Math. the problem of determining which numbers from a given collection of numbers have been added together to yield a specific sum: used in cryptography to encipher (and sometimes decipher) messages. [so called because the problem is similar to… …   Universalium

  • knapsack problem — Math. the problem of determining which numbers from a given collection of numbers have been added together to yield a specific sum: used in cryptography to encipher (and sometimes decipher) messages. [so called because the problem is similar to… …   Useful english dictionary

  • Continuous knapsack problem — The continuous knapsack problem, also known as the fractional knapsack problem, is similar to the classic knapsack problem but in this problem fractions of an item can be put into the knapsack. The problem is as following: Given a knapsack with… …   Wikipedia

  • Knapsack — steht für: Knapsack (Hürth), ein Stadtteil von Hürth, nahe Köln den dort ansässigen Chemiepark Knapsack Knapsack Problem, siehe Rucksackproblem Knapsack Verfahren, siehe Merkle Hellman Kryptosystem einen Dampflok Typ der Friedrich Krupp AG, siehe …   Deutsch Wikipedia

  • Knapsack (disambiguation) — The word knapsack can refer to: * a backpack * Knapsack, Germany, a locality of Hürth, Rhine Erft district, North Rhine Westphalia * the knapsack problem, a math problem:* the subset sum problem, a special case of the above:* Naccache Stern… …   Wikipedia

  • knapsack — [17] The sack of knapsack is no doubt essentially the same word as English sack, but the knap presents slightly more of a problem. The term was borrowed from Low German knappsack, and so probably knapprepresents Low German knappen ‘eat’ – the bag …   The Hutchinson dictionary of word origins

  • knapsack — [17] The sack of knapsack is no doubt essentially the same word as English sack, but the knap presents slightly more of a problem. The term was borrowed from Low German knappsack, and so probably knapprepresents Low German knappen ‘eat’ – the bag …   Word origins

  • List of knapsack problems — The knapsack problem is one of the most studied problems in combinatorial optimization, with many real life applications. For this reason, many special cases and generalisations have been examined. Common to all versions are a set of n items,… …   Wikipedia

  • Merkle–Hellman knapsack cryptosystem — The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.[1] Although its ideas are elegant, and far simpler than RSA, it has been broken.[2] Contents 1… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”