Diskussion:Rucksackproblem

Die Beschreibung des Rucksack Problems ist recht spezifisch. Es bezieht sich auf das Subset sum Problem. Jemand sollte sich der Sache mal annhemen, um es allgemeiner zu verfassen. Leider fehlt mir selber dazu die Zeit.

Bis dahin soll man sich, sofern man der englischen Sprache maechtig ist, den Weblink anschauen.

Subset Sum hat einfach nur keine Gewichtsfunktion (bzw. diese ist identisch mit der Kostenfunktion) und ist damit ein Spezialfall von Knapsack. --zelle

Die Bezeichnung "Problem" kommt mir verdammt denglisch vor. Das im Englischen in der Mathematik gebrauchte Wort "problem" heißt auf Deutsch "Aufgabe", nicht Problem!

Mag sein; da es sich aber um eine Standarduebersetzung handelt, die in der Literatur weit verbreitet ist, ist das nicht mehr zu aendern. --Mellum 17:30, 22. Jul 2004 (CEST)

...-problem ist in Fachkreisen (zumindest in denen in denen ich verkehre) die absolut gängige Bezeichnung. Ich habe z.B. noch nie jemanden "Rucksack-Aufgabe" sagen hören. Ich habe mal mein ältestes Fachbuch (1986) zu Rate gezogen und auch da hieß das schon Rucksack-Problem. Allerdings fand ich auch unter "O" den Eintrag: Optimierungsaufgabe (=Optimierungsproblem). StS

Darf ein Gegenstand nur einmal oder beliebig oft genommen werden? nur einmal -> wert von kapazität=4 ist falsch beliebig oft -> die formalisierung als entscheidungsproblem ist falsch, da man ein Element aus einer Menge nur einmal nehmen kann. --poc

Das Beispiel ist falsch, jeder Gegenstand darf nur einmal gewählt werden. Habe das korrigiert, allerdings ist das korrigierte ziemlich nichtssagend... Da sollte man vielleicht mal was schöneres suchen.

So wie das Problem formuliert ist, darf jeder Gegenstand nur einmal gewählt werden, da die Gewichte und Kosten hier als Funktion auf der "Gegenstands"-Menge definiert sind. Es gibt aber noch ein allgemeines Knapsack-Problem, das auch NP-Vollständig ist, bei dem jedes Element mehrfach "eingepackt" werden kann. Dafür eignet sich am besten eine Darstellung mit Gewichts- und Kostenvektoren (Beispielsweise w und c). Gesucht wird dann der Vektor x der w*x maximiert und für den c*x <= K gilt. Der Vektor x kann natürlich auch so definiert werden, dass er nur Nullen und Einsen enthalten darf, was das Knapsack-Problem dann wieder wie gehabt spezialisieren würde.--zelle

Nachtrag: Da beide Probleme NP-vollständig sind, sind sie ohnehin nur ein Polynom voneinander entfernt. ;-)

Frage: Wie würde sich denn die Komplexität verändern, wenn man davon ausginge, dass man mehrere Rucksäcke hat und die Gegenstände (bei jeweils unterschiedlichen Maximalgewichten der Rucksäcke) optimal auf diese verteilen müsste? --Tetrapak 16:41, 1. Aug 2006 (CEST)

1. Wir sind kein Forum, in dem solche Fragen beantwortet werden sollen.
2. Es wird höchstens schwieriger, liegt aber weiterhin in NP, ist also auch NP-vollständig... --Koethnig 22:33, 1. Aug 2006 (CEST)

DP Matrix und Laufzeitbetrachtung

Ich habe da meine Zweifel zum Programm, dass das Rucksackproblem mit Hilfe dynamischer Programmierung lösen soll. Wie es scheint laufen die Indizes der Matrix R ab 1 los, dies kann man jedenfalls anhand des Index i nachvollziehen, da wir es mit einer (n+1)×B Matrix zu tun haben würde i=n auf das Feld R(n+1,?) führen, was ausschließt, dass die Matrix einen Index i=0 haben kann. Da j von 1 bis B läuft, kann ich auch davon ausgehen, dass es keinen Index j=0 gibt. Was passiert aber wenn bei der IF-Bedingung w(i)=j gilt, dann muss ich bei der Maximumsbildung auf R(i+1,j-w(i)), also R(i+1,0) zugreifen. Dies darf es aber nicht geben. Was denkt ihr dazu? --thkote

Komisch ist auch, das in der FOR-Schleife j die Werte 1 bis B annimmt. B ist aber eine reelle Zahl! ---MRK

Da das DP-Beispiel nur für ganzzahlige Werte funktioniert, muss B in dem Fall imo keine reelle Zahl sein. Was mich mehr wundert ist aber, dass unten steht, B wachse exponentiell mit der Größe der Eingabemenge. Da B aber oben als die obere zulässige Grenze für's Gesamtgewicht definiert ist, sehe ich da keine Abhängigkeit von der Größe der Eingabemenge - es sei denn, B meint in diesem Kontext was anderes. --KullerhamPster 13:53, 14. Mai 2008 (CEST)

Wahrscheinlich ist mit dem Satz gemeint, dass das Problem immernoch NP-vollständig ist, auch wenn der DP-Algorithmus auf den ersten Blick nach Polytime aussieht. Man bezeichnet die Laufzeit solcher Algorithmen auch als pseudo-polynomiell, siehe auch http://en.wikipedia.org/wiki/Pseudo-polynomial_time --Gms 23:30, 14. Mai 2008 (CEST)

Dass man irgendwie begründen muss/sollte, warum der Algorithmus dennoch NP-vollständig ist, sehe ich auch so. Nur verstehe ich die Begründung nicht. Wenn B wirklich nur die "Kapazität" des Rucksacks darstellt, dann ist diese Größe doch unabhängig von der Problemgröße (die durch die Anzahl der zur Wahl stehenden Teile definiert wird), oder sehe ich das falsch? --KullerhamPster 09:40, 15. Mai 2008 (CEST)

Das Argument ist folgendes: Die Größe einer Probleminstanz, also die Eingabelänge, ist, bei einer sinnvollen Kodierung der Zahlen (z.B. binär), O(n) (also n Gegenstände) mal O(log B) (jeder Nutzwert bzw. Gewicht ist maximal B groß) plus O(log B) (also das maximale Gewicht. Und der Zusammenhang zwischen dem Eingabe der Länge O(n log B) und der Laufzeit O(n B) ist eben nicht polynomiell sondern exponentiell. D.h. die Laufzeit wächst nicht polynomiell in Abhängigkeit der Eingabe. Das gilt allerdings nicht, wenn die Anzahl der Stellen der Zahlen beschränkt ist (z.B. auf 32 Bit bei Binärkodierung). Deshalb bezeichnet so einen Algorithmus auch als pseudo-polytime. --Gms 18:14, 15. Mai 2008 (CEST)

Die Rekursionsformel ist mir sehr suspekt.

Da ich das heute gelernt habe (für eine Klausur die ich bald schreibe), habe ich mir u.a. auch diese Saeite angeguckt. Nun habe ich das ganze verstanden, allerdings ist mir die Beispielformel (der Pseudoce) doch sehr suspekt. Man möchte bestimmen welche Objekte man in den Rücksack des Gewichts B packen kann. Man fange mit i=1 und höre mit i=n auf (und nicht umgekehrt). So laufe man alle Möglichkeiten ab, auch für alle Gewichtsverteilungen und bestimme am Ende die Lösung R(n,B) bzw daraus die Lösung R(k,B)für die Teilmenge K (1,...,k). Das was da steht verstehe ich nicht so ganz. Man fängt mit i=20 an und betrachtet das Ergebnis in i+1=21, dass nicht in der Menge liegt? irgendwie Sinnfrei, zumindest für mich. Wozu mal für 1,...,B abläuft kann ich gern demjenigen Erklären der ist wissen möchte. Es geht darum einfach nicht durch Rekursion ergebnisse mehrmals zu berechnen, sondern diese aus der abgespeicherten Wertetabelle abzulesen und diese erstellt man eben, in dem man für i=1 die Werte F(1,g=1,....,B) ausrechnet. Für i=2 greift man dann teilweise auf die Werte zurück, die man schon mit i=1 berechnet hat. Und so geht das weiter bis i=n. Demnach verstehe ich die Formel hier bei euch nicht, bzw. sehe da keinen Sinn. Was soll denn die Ausgabe R(1,B) liefern? Wenn man wissen will, die die Obejkte 1,....,k in den Rücksack passen, geht man in der Tabelle eigentlich von hinten nach vorne los und packt somit die Objekte in den Rücksack.

Wenn ihr natürlich da anderer Meinung seid, bitte um Comments, gern auch auf meine eMailadresse: Wladi_Dortmund@web.de

Gruß Wladi

PS: Wobei bei für Fälle i=0, j=0 und j<0 die Sonderfälle beachten musst. Bei j<0 packt man das Objekt nicht rein, bei j=0 muss man die Funktionswerte vergleichen und bei i=0 haben wir den Funktionswert von 0, wobei die Entscheindung, ob das Objekt genommen werden muss, nicht klar bleibt bzw nicht getroffen werden muss.

Wofür $R(i,j)$ bzw. $R(1,B)$ steht, steht nun im Artikel. Die Initialisierung der n+1'ten Zeile mit 0 macht Sinn, da sie der Ermittlung des maximalen Nutzwerts bei leerer Gegenstandsmenge entspricht.

PS: Beiträge auf der Diskussionseite bitte beim nächsten Mal signieren. --Gms 23:05, 14. Mai 2008 (CEST)

Alternative Lösung?

Beim ersten Betrachten des Rucksack-Problems kam mir der Gedanke ob man es nicht schneller durch Sortieren lösen könnte. Und zwar bräuchte man nur das Verhältnis Wert/Gewicht von jedem Gegenstand berechnen und dann absteigend mit dem größten Verhältnis in eine Liste sortieren. Dann bräuchte man nur noch die Liste von oben nach unten abarbeiten und so viel reinpacken wie möglich. Das dürfte im Allgemeinen schnell akzeptable Ergebnisse liefern, ich könnte mir aber vorstellen dass unter ganz bestimmten Umständen ein einzelner wertvoller Gegenstand gerade so den Platz für viele weniger wertvolle Gegenstände versperrt, die aber in der Summe wertvoller wären als der Einzelne (zumindest wenn man es geometrisch betrachtet und statt Gewicht Volumen als Anschauung benutzt). --Amogorkon 12:11, 7. Nov. 2008 (CET)

die sortierung dürfte bei einer relativ grossen kapazität und vielen unterschiedlichen objekten eine schnelle möglichkeit aufzeigen eine nahe am optimum liegende lösung zu finden. leider dürfte es sich fast imemr nur um eine annäherung handeln. aber gerade wenn es relativ wenige objekte gibt und/oder der rucksack ziemlich klein ist, dürfte es zu dem problem kommen, das du geschildert hast. leider steigt aber die mögliche anzahl der objekt kombinationen sehr rasch an, dass ein plumpes ausprobieren kaum möglich ist. die sortierung könnte jedoch einen fitness-wert geben, mit dem man weiterarbeiten kann. zumindest als wert, der auf jeden fall erreichbar ist. ein einfacher dursschnitt der werte kann höher liegen als das maximal erreichbare ergebnis (siehe ein 50t schwerer goldbarren , der als "option" daneben liegt aber einfahc nicht in den rucksack passt und einen wert hat, der alles andere brutto und netto übertrifft) Elvis untot 10:52, 12. Nov. 2008 (CET)

Ein Greedy-Algorithmus dieser Art (Sortierung nach Effizienz) kann beliebig schlechte Ergebnisse liefern. Ein einfaches Beispiel dafür: Kapazität des Rucksacks = 100, Gegenstand 1 mit Gewicht 1 und Wert 2, Gegenstand 2 mit Gewicht 100 und Wert 100. Der Greedy-Algorithmus würde Gegenstand 1 einpacken, aber viel besser wäre es Gegenstand 2 zu nehmen. --91.115.225.166 14:01, 6. Apr. 2010 (CEST)