Das Rucksackproblem

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Das Rucksackproblem

    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='&quot']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

  • 2^n stimmt schon. n! ist (glaube ich) nur, wenn man ein Objekt auch mehrmals reinpacken kann. Da das aber hier nicht der Fall ist, sind es "nur" 2^n.

    Ich versuche mal zu erläutern was die da Vorschlagen:
    Maximalgewicht is 10.
    Zuerst wird das 1. Objekt (Gewicht 12kg Wert pro kg = 5€) bedacht --> 2 Möglichkeiten:
    Objekt 1 mitnehmen --> Lösung entfällt da das Gewicht zu groß ist
    Objekt 1 nicht mitnehmen --> Lösung wird weiter verfolgt.
    Nun das 2. Objekt (8kg und 3€ pro kg) --> Aufgrund der vorherigen Ausschlüße gibt es 2 Möglichkeiten:
    Objekt 2 mitnehmen --> Lösung wird weiter verfolgt.
    Objekt 2 nicht mitnehmen --> Lösung wird weiter verfolgt.
    Nun das 3. Objekt (5kg und 2€ pro kg) --> Aufgrund der vorherigen Ausschlüße gibt es 4 Möglichkeiten:
    Objekt 2 mitnehmen Ojekt 3 mitnehmen --> Lösung entfällt da das Gewicht zu groß ist
    Objekt 2 nicht mitnehmen Ojekt 3 mitnehmen --> Lösung wird weiter verfolgt (zwar weniger Gewinn, doch dafür mehr Platz).
    Objekt 2 mitnehmen Ojekt 3 nicht mitnehmen --> Lösung wird weiter verfolgt.
    Objekt 2 nicht mitnehmen Ojekt 3 nicht mitnehmen --> Lösung wird weiter verfolgt.
    Nun das 4. Objekt (3kg und 1€ pro kg) --> Aufgrund der vorherigen Ausschlüße gibt es 6 Möglichkeiten:
    3, 4 --> WICHTIG! Lösung entfällt, da es eine Kombination gibt, die gleich oder weniger wiegt und mehr Gewinn bringt! Nämlich: nur das Objekt 2 mitnehmen
    3 --> Lösung wird weiter verfolgt.
    2, 4 --> Lösung entfällt da das Gewicht zu groß ist
    2 --> Lösung wird weiter verfolgt.
    4 --> Lösung wird weiter verfolgt (zwar weniger Gewinn, doch dafür mehr Platz).
    nix mitnehmen --> Lösung wird weiter verfolgt.

    Verstanden?

  • Hallo,

    bei der Umsetzung in einen Quelltext habe ich noch ein Problem. Wie kann ich wirklich alle Möglichkeiten in einer Scheife durchgehen? Düfte man jedes Objekt nur einmal einpacken, so wäre es leicht. Wie mache ich das aber wenn man jede Objekt oft einpacken darf? Die Begrenzung wäre natürlch die Gewichtsschranke.

    Realisieren wüde ich das ganze gerne in C++. Mir fehlt halt einfach der Ansatz das durchzugehen. Kennt ihr Seiten die sich damit beschäftigen?

    Vielen Dank fü deine bisherige Hilfe

  • 2^n statt m!

    Hi,

    falls das noch aktuell ist:

    2^n Möglichkeiten ergeben sich, wenn man die Reihenfolge nicht berücksichtigt. Bei n! berücksichtig man die Reihenfolge der Objekte.

    Das es beim RP völlig wurscht ist, in welcher Reihenfolge die Objekte im Rücksack liegen, also 2^n Möglichkeiten.

    Gruß,

    Kwyjibo