Diskussion:Rucksackproblem

Teilmenge/echteTeilmenge

Müsste K nicht eine echte Teilmenge von U sein? --80.141.203.68 01:45, 14. Nov. 2012 (CET)

Problembeschreibung

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)

Auch wenn die Bemerkung schon 4 Jahre alt ist, interessiert es ja vielleicht den einen oder anderen, der sich auch diese Gedanken gemacht hat: In dieser Form kann der Algorithmus beliebig schlechte Ergebnisse liefern, wie schon gezeigt. Modifiziert man allerdings den Algorithmus so, dass er entweder die so gefundene Lösung oder das Element, das als nächstes in die Lösung aufgenommen worden wäre, ausgibt (je nachdem, welche der beiden Lösungen besser ist), ergibt sich ein 2-Approximationsalgorithmus, d.h. die Lösung ist mindestens halb so gut wie eine Optimallösung --91.22.15.236 03:31, 14. Jul. 2012 (CEST)

Das im Moment eingestellte Bild zur Illustration legt nahe, dass sich das Problem auch genauso gut durch absteigendes Sortieren der Elemente nach (Nutzen/Gewichtseinheit) und anschließendem Einpacken, beginnend mit dem Element mit dem höchsten Nutzen, lösen ließe. Denn für das Beispiel aus der Illustration kommt man mit der von mir geschilderten Lösung zum selben Ergebnis, wie mit dem dynamischen Algorithmus. --2003:E6:6F2D:F300:4587:F9C1:F119:D7DA 20:19, 12. Jun. 2019 (CEST)

Formel falsch?

Hallo, meiner Meinung nach müsste im bsp für dyn prog for i = 1 ..n heißen MfG -- 92.226.63.115 18:04, 22. Jul. 2011 (CEST)

nein, muss i=n..1 heißen.

Aber nochmal was anderes, habe den verlinkten Artikel [1] gelesen. Kann es sein, dass der Autor sich bei einer Sache verschrieben hat? Man hat seine Liste mit Pareto-Optimalen Punkten und dann fügt man ein neues Objekt hinzu. Soweit so klar. Nun meint der Autor aber, dass man die neue Liste mit Pareto-optimalen Punkten bekommt, wenn man die Punkte beider Listen nimmt und dann die Punkte löscht, die links oberhalb schon einen Punkt haben. Es müssen doch die Punkte gelöscht werden, die OBERHALB und nicht LINKS OBERHALB schon einen Punkt haben, oder?--svebert 21:55, 4. Aug. 2011 (CEST)

Beschriebenes Problem wirklich NPC und nicht nur NP-hart?

In dem Artikel wird beschrieben, dass beim Rucksackproblem der maximale Nutzen gesucht ist, bei dem das Gewicht nicht einen bestimmten Wert überschreitet. Die NPC-Beweise dazu, die ich bisher gesehen habe, suchen jedoch nicht den maximalen Nutzen sondern einen Mindestnutzen. Das es NP-hart ist lässt sich bei beiden gleichermaßen nachweisen. Aber wie wird die NP-Zugehörigkeit bewiesen? Normalerweise erfolgt der Nachweis ja durch das raten einer Lösung durch eine Orakelturingmaschine und anschließender Verifikation in polynomieller Zeit. Beim Mindestnutzen ist dies auch problemlos möglich, da man einfach das Gewicht und den Wert der gewählten Objekte mit den Grenzen vergleichen muss. Beim maximalen Nutzen ist zwar das vergleichen mit der Gewichtsgrenze möglich, aber der maximale Nutzen nicht (mir fällt da kein polynomieller Algorithmus ein). Ist da etwas bekannt? (nicht signierter Beitrag von 92.231.186.80 (Diskussion) 16:08, 22. Aug. 2011 (CEST))

Eine möglichkeit ist es das problem auf ein anderes zurückzuführen von dem man weiss dass es npc/hart ist (nicht signierter Beitrag von 87.155.95.216 (Diskussion) 23:01, 7. Okt. 2011 (CEST))

Link zu Erklärung entfernt

Ich habe diesem Artikel vor einiger Zeit einen Link zu einer relativ ausführlichen - von mir persönlich verfassten - Erklärung hinzugefügt. Dieser Link wurde von einem unbekanntem User wegen "Linkspam" wieder entfernt. Da der Artikel wirklich ausschließlich das angesprochene Thema behandelt und dabei deutlich ausführlicher ist als der Artikel von Wikipedia selbst, verstehe ich diese Reaktion nicht. Bitte um Rückmeldung. http://www.proggen.org/doku.php?id=algo:knapsack (sollte er tatsächlich als Spam angesehen werden, bitte natürlich auch hier entfernen) (nicht signierter Beitrag von 84.112.234.234 (Diskussion) 00:02, 15. Okt. 2012 (CEST))

Allgemeinverständlichkeit

Wenn der Artikel, wie von Wikipedia erwartet, halbwegs allgemeinverständlich sein soll, dann sollte irgendwo auch mal klargestellt werden, dass bisher kein Weg bekannt ist, um das Rucksackproblem zu lösen. (offensichtlich wird es selbst bei ganzen Zahlen schon schwierig). Wenn das so stimmt, schreibt das doch bitte mal explizit mit rein. Bisher entsteht für Nicht-Experten der Eindruck, dass eine Lösung des Problems in endlicher Zeit möglich wäre. --Max schwalbe (Diskussion) 20:37, 7. Dez. 2017 (CET)

Und noch etwas wäre für den Nichtexperten interessant: Ab wann tritt der Fall ein, dass das Rucksackproblem in endlicher Zeit nicht mehr lösbar ist? Bei 3 oder 4 Gegenständen lässt sich ja mittels Errechnen und Vegleich aller möglichen Kombinationen spätestens beim Probieren der letzten Kombination eine eindeutige Lösung noch finden. --Max schwalbe (Diskussion) 21:11, 7. Dez. 2017 (CET)

Das Rucksackproblem ist immer in endlicher Zeit lösbar, da eine endliche Menge nur endlich viele Teilmengen hat. Die kann man natürlich in endlicher Zeit alle durchprobieren. -- HilberTraum (d, m) 21:51, 7. Dez. 2017 (CET)

Ok dann war "endliche Zeit" der falsche Begriff. Ich meinte eher, ob das Problem in der Praxis lösbar ist oder nicht. Da stößt das Rucksackproblem ja offenbar schnell an seine Grenzen der Lösbarkeit, sonst würde es nicht zu den NP-vollständigen Problemen der Informatik zählen. Wobei das natürlich von der Rechenleistung des Computers abhängt, klar. Insofern kann man die Frage gar nicht eindeutig beantworten. Würde mich trotzdem mal interessieren, bis zu welcher Zahl an Gegenständen man das Rucksackproblem mit einem haushaltsüblichen PC noch innerhalb von 24 Stunden berechnen kann? Da die benötigte Rechenzeit mit der Zahl der Gegenstände exponentiell ansteigt, dürften es dann wohl nur überraschend wenige Gegenstände sein, für die sich eine Lösung in 24 Stunden noch finden lässt. Das könnte ein schöne sbEispiel sein, um das Rucksackproblem bzw. die NP-Vollständigkeit zu veranschaulichen. --Max schwalbe (Diskussion) 17:54, 8. Dez. 2017 (CET)

Ja, das wären sicher sinnvolle Ergänzungen für den Artikel. Müsste halt jemand^TM mal recherchieren und einbauen. -- HilberTraum (d, m) 19:47, 8. Dez. 2017 (CET)