Hallo,
ich versuche mich in die Thematik des Rucksackproblemes einzuarbeiten und möchte nun versuchen Lösungsansätze zu finden. Habe versucht mich auf einigen Quellen schlau zu machen (Wiki und zb dieser Seite: [font='"']http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php ). Ich muss allerdings zugeben das mir die Lösung nich einleuchtend ist. Warum gibt es zb 2 hoch n und nicht n! Möglichkeiten die Objekte zu kombinieren?
Mein Lösungsansatz wäre das Durchprobieren aller möglichkeiten. Um zur richtigen Lösung zu kommen müsste ich bei jeder Möglichkeit prüfen ob das Gewicht nicht das maximalgewicht überschreitet und ob der Nutzwert nicht geringer als der bisher maximalst ermittelte Nutzwert ist.
Nun ist aber klar das es zu viele Möglichkeiten gibt und die Lösung deswegen nicht optimal ist. Ich habe schon was von Backtracking gelesen.. Außerdem bietet obige Seite ja einen Ansatz. Kennt ihr alternative Quellen? Das mit den [/font]Pareto-optimalen Punkten ist für mich nicht verständlich.
Was ich glaube verstanden zu haben ist: Das Maximal-Gewicht wird zunächst nicht beachtet. Es wird zunächst nur geprüft ob es eine andere Kombination gibt die gleichschwer oder leichter ist und mehr Nutzen hat. Die Punkte die bei gleichem oder geringeren Gewicht als andere Punkte noch den größeren Nutzwert haben nennt man Pareto-optimale Punkte. Nur wie ermittelt man diese nun rechnerrisch?
Danke für eure Hilfe
ich versuche mich in die Thematik des Rucksackproblemes einzuarbeiten und möchte nun versuchen Lösungsansätze zu finden. Habe versucht mich auf einigen Quellen schlau zu machen (Wiki und zb dieser Seite: [font='"']http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php ). Ich muss allerdings zugeben das mir die Lösung nich einleuchtend ist. Warum gibt es zb 2 hoch n und nicht n! Möglichkeiten die Objekte zu kombinieren?
Mein Lösungsansatz wäre das Durchprobieren aller möglichkeiten. Um zur richtigen Lösung zu kommen müsste ich bei jeder Möglichkeit prüfen ob das Gewicht nicht das maximalgewicht überschreitet und ob der Nutzwert nicht geringer als der bisher maximalst ermittelte Nutzwert ist.
Nun ist aber klar das es zu viele Möglichkeiten gibt und die Lösung deswegen nicht optimal ist. Ich habe schon was von Backtracking gelesen.. Außerdem bietet obige Seite ja einen Ansatz. Kennt ihr alternative Quellen? Das mit den [/font]Pareto-optimalen Punkten ist für mich nicht verständlich.
Was ich glaube verstanden zu haben ist: Das Maximal-Gewicht wird zunächst nicht beachtet. Es wird zunächst nur geprüft ob es eine andere Kombination gibt die gleichschwer oder leichter ist und mehr Nutzen hat. Die Punkte die bei gleichem oder geringeren Gewicht als andere Punkte noch den größeren Nutzwert haben nennt man Pareto-optimale Punkte. Nur wie ermittelt man diese nun rechnerrisch?
Danke für eure Hilfe