www.wikidata.de-de.nina.az
Das Rucksackproblem auch englisch knapsack problem ist ein Optimierungsproblem der Kombinatorik Aus einer Menge von Objekten die jeweils ein Gewicht und einen Nutzwert haben soll eine Teilmenge ausgewahlt werden deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht uberschreitet Unter dieser Bedingung soll der Nutzwert der ausgewahlten Objekte maximiert werden Das Rucksackproblem Welche der Gewichte konnen in den Rucksack mit Maximallast von 15 kg gepackt werden so dass der Geldwert maximal wird Losung in diesem Fall Alle Gewichte ausser dem schwersten einpacken Die Entscheidungsvariante des Rucksackproblems fragt ob ein zusatzlich vorgegebener Nutzwert erreicht werden kann Sie gehort zur Liste der 21 klassischen NP vollstandigen Probleme von denen Richard Karp 1972 die Zugehorigkeit zu dieser Klasse zeigen konnte 1 In der Kryptographie wird haufig eine andere Entscheidungsvariante betrachtet Dabei werden nur die Gewichte betrachtet und es wird gefragt ob es eine Teilmenge der Objekte gibt die einen vorgegebenen 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 1 Anschauung 2 Mathematische Formulierung 3 Losung durch dynamische Programmierung 4 Losung mittels Profitabilitatsindex 5 Anwendungen 6 Siehe auch 7 Literatur 8 Weblinks 9 EinzelnachweiseAnschauung BearbeitenDas Rucksackproblem hat seinen Namen aus folgender Anschauung heraus erhalten Es sind verschiedene Gegenstande mit einem bestimmten Gewicht und einem Nutzwert gegeben Aus diesen Gegenstanden soll nun eine Auswahl getroffen werden die in einen Rucksack mit einer vorgegebenen Gewichtsschranke mitgenommen werden konnen 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 BearbeitenGegeben ist eine endliche Menge von Objekten U displaystyle U nbsp Durch eine Gewichtsfunktion w displaystyle w nbsp und die Nutzenfunktion v displaystyle v nbsp wird den Objekten ein Gewicht und ein festgelegter Nutzwert zugeordnet w U R displaystyle w colon U rightarrow mathbb R nbsp v U R displaystyle v colon U rightarrow mathbb R nbsp Des Weiteren gibt es eine vorgegebene Gewichtsschranke B R displaystyle B in mathbb R nbsp Gesucht ist eine Teilmenge K U displaystyle K subseteq U nbsp die die Bedingung u K w u B displaystyle sum u in K w u leq B nbsp einhalt und die Zielfunktion u K v u displaystyle sum u in K v u nbsp maximiert Der Spezialfall v w displaystyle v w nbsp fuhrt auf das Teilsummenproblem Losung durch dynamische Programmierung BearbeitenSind die Gewichte ganzzahlig so lasst sich der optimale Wert des Rucksackproblems auch mittels dynamischer Programmierung losen Seien dazu 1 n displaystyle 1 ldots n nbsp die Elemente von U displaystyle U nbsp Eingabe U B w v wie oben beschrieben R 1 n 1 0 B Matrix mit Eintragen 0 FOR i n 1 FOR j 1 B IF w i lt 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 displaystyle R i j nbsp ist der maximale Nutzwert bei maximal moglichem Gesamtgewicht von j displaystyle j nbsp bei Berucksichtigung einer Teilmenge von Gegenstanden aus der Teilsequenz i n displaystyle i n nbsp der Gesamtsequenz aller Gegenstande 1 n displaystyle 1 n nbsp Also ist der maximale Nutzwert bei Berucksichtigung einer Teilmenge aller Gegenstande in der Zelle R 1 B displaystyle R 1 B nbsp nach Beendigung des Algorithmus gespeichert In jeder Zeile i displaystyle i nbsp der Matrix R displaystyle R nbsp wird uber die beiden Falle optimiert ob der Nutzwert maximal vergrossert werden kann wenn der Gegenstand i displaystyle i nbsp mit dem Gewicht w i displaystyle w i nbsp dem Rucksack hinzugefugt oder er nicht aufgenommen wird Im ersten Fall erhoht sich der Nutzwert um v i displaystyle v i nbsp Um den Inhalt des Rucksacks mit dem maximalen Nutzwert zu bestimmen kann er rekonstruiert werden indem die Berechnung des Optimums in R 1 B displaystyle R 1 B nbsp mittels Backtracking zuruckverfolgt wird Die Korrektheit folgt aus der folgenden Beobachtung Sei K displaystyle K star nbsp eine optimale Losung Dann ist K i displaystyle K star backslash i nbsp eine optimale Losung fur die Instanz U i displaystyle U backslash i nbsp mit Maximalgewicht B w i displaystyle B w i nbsp Der Algorithmus benotigt aufgrund der verschachtelten for Schleifen die uber n und B iterieren eine Laufzeit von O n B displaystyle O n cdot B nbsp Hierbei ist zu beachten dass B eine zu seiner Eingabelange exponentiell wachsende Grosse und somit die Laufzeit pseudopolynomiell ist Das folgende Beispiel zeigt eine Implementierung des Algorithmus in der Programmiersprache C 2 include lt iostream gt using namespace std Diese Funktion pruft ob es eine Aufteilung der Menge mit gleichen Summen gibt und gibt dann true zuruck sonst false bool findPartition int numbers int n int sum 0 for int i 0 i lt n i for Schleife die die Summe der Zahlen berechnet sum numbers i if sum 2 0 Wenn die Summe ungerade ist wird false zuruckgegeben return false bool part new bool sum 2 1 Deklariert ein Array in dem gespeichert wird ob die Zahlen 0 1 2 als Summe einer Teilmenge der gegebenen Zahlen dargestellt werden konnen for int i 0 i lt sum 2 i for Schleife die das Array initialisiert part i false for int i 0 i lt n i for Schleife die die Indexe der Zahlen durchlauft for int j sum 2 j gt numbers i j In dieser for Schleife wird gepruft ob Halbe Gesamtsumme Zahl mit Index i als Summe einer Teilmenge von Zahlen mit Index kleiner als i dargestellt werden kann if part j numbers i j numbers i Wenn die Summe j Zahl mit Index i dargestellt werden kann oder die Zahl mit Index i gleich j ist wird das Element fur die Summe j auf true gesetzt part j true return part sum 2 Gibt das Element fur die halbe Gesamtsumme der Zahlen zuruck Dieses Element vom Typ bool gibt an ob diese Summe dargestellt werden kann Hauptfunktion die das Programm ausfuhrt int main int numbers 1 3 3 2 3 2 int n sizeof numbers sizeof numbers 0 Variable fur die Anzahl der Zahlen if findPartition numbers n Wenn eine Aufteilung mit gleichen Summen gefunden wurde cout lt lt Es gibt eine Aufteilung mit gleichen Summen lt lt endl Ausgabe auf der Konsole else cout lt lt Es gibt keine Aufteilung mit gleichen Summen lt lt endl Ausgabe auf der Konsole Losung mittels Profitabilitatsindex BearbeitenIn der Praxis wird ein Ranking der Objekte nach Profitabilitatsindex vorgenommen P I W R displaystyle PI W div R nbsp PI Profitabilitatsindex W Generierter Wert hier Nutzwert R Verbrauchte Ressourcen hier Gewicht Dann werden moglichst viele Objekte gewahlt beginnend mit dem Objekt mit hochstem Profitabilitatsindex Dies fuhrt bei ganzzahligen Problemen nicht immer zur optimalen Losung ist aber sehr praktikabel Bei dieser Methodik handelt es sich um einen Greedy Algorithmus Anwendungen BearbeitenViele reale Situationen lassen sich mit Hilfe der Losung dieses Problems mathematisch klaren Oft steht eine begrenzte Kapazitat zur Verfugung welche nicht die gesamte Nachfrage befriedigen kann Man denke z B an einen Lkw der viele verschiedene Guter mit einem bestimmten Gewinn transportieren soll aber wegen der begrenzten Lademenge nicht alle Guter aufnehmen kann Der Besitzer des Lkws wird die Ladung so wahlen wollen dass der Gewinn maximal ausfallt Siehe auch BearbeitenGreedy Algorithmus Optimierungsproblem Teilsummenproblem PartitionsproblemLiteratur BearbeitenHans Kellerer Ulrich Pferschy David Pisinger Knapsack Problems Springer Berlin u a 2004 ISBN 3 540 40286 1 Silvano Martello Paolo Toth Knapsack problems Algorithms and computer implementations J Wiley Chichester u a 1990 ISBN 0 471 92420 2 Buch als PDF und Fortran Quelltext zum Buch Weblinks BearbeitenDas Rucksackproblem Knapsack Problem Ausfuhrliche Erklarung mit Grafiken und Beispiel ImplementierungEinzelnachweise Bearbeiten Richard M Karp Reducibility Among Combinatorial Problems In Springer Hrsg Proceedings of a symposium on the Complexity of Computer Computations Yorktown Heights New York 1972 S 85 103 springer com GeeksforGeeks 0 1 Knapsack ProblemKarps 21 NP vollstandige Probleme Erfullbarkeitsproblem der Aussagenlogik Cliquenproblem Mengenpackungsproblem Knotenuberdeckungsproblem Mengenuberdeckungsproblem Feedback Arc Set Feedback Vertex Set Hamiltonkreisproblem Integer Linear Programming 3 SAT graph coloring problem Covering by cliques Problem der exakten Uberdeckung 3 dimensional matching Steinerbaumproblem Hitting set Rucksackproblem Job sequencing Partitionsproblem Maximaler Schnitt Abgerufen von https de wikipedia org w index php title Rucksackproblem amp oldid 234077642