Diskussion:Rucksackproblem
aus Wikipedia, der freien Enzyklopädie
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.
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.
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)
- Wir sind kein Forum, in dem solche Fragen beantwortet werden sollen.
- Es wird höchstens schwieriger, liegt aber weiterhin in NP, ist also auch NP-vollständig... --Koethnig 22:33, 1. Aug 2006 (CEST)
