Rucksackproblem

[buff222]

Hallo zusammen,
ich habe ein kleines Problem mit einem Schulprojekt.
Ich soll das Rucksackproblem programmieren. Das Grundprinzip vom Rucksackproblem kenn ich, hab aber keine Ahnung wie ich das Rucksackproblem in Delphi umsetzen kann.
Die Vorgaben wieviel kilo getragen werden Können, wie schwer und welchen Wert die Objekte haben können auch im programm vorgegeben werden, falls es die Sache einfacher macht.

Ich brauche ganz dringend Hilfe bei der Programmierung, da ich das allein nicht hinkriege und mein Lehrer mir auch nicht gerade weiterhilft. Kleine Tipps könnten auch Hilfreich sein.

Ich bedank mich schonmal für eure Antworten

[dino]

was ist denn das RucksackProblem???

[Luckie]

Hast du Problme beim Code oder schon beim Konzept? Wenn bei ersteren poste bitte deine konkrte Frage / problem zum Quellcode. Hast du Problem emit dem Konzept, wäre es sehr hilfreich, wenn du uns sagst, wie weit du schon bist und wo du jetzt Probleme hsst.

Aber im Moment kann man dir so keine Hilfe geben, weil du uns nicht sagst wo konkret du Probleme hast.

[freak4fun]

Zitat von dino:

was ist denn das RucksackProblem???

Man sollte Antworten posten und nicht Fragen. Rucksackproblem

MfG
freak

[dino]

man sollte das schon als Fragensteller dazuposten...

um welche gewichte handelt es sich und wieviel sind sie wert?

[Luckie]

Zitat von dino:

um welche gewichte handelt es sich und wieviel sind sie wert?

Absolut irrelevant die Frage.

Man könnte einfach einen BruteForce Algorithmus auf das Problem los lassen und alle Möglichkeiten durchprobieren. Wäre natürlich so ziemlich das uneleganteste was es gibt, dafür aber ziemlich sicher und robust.

[buff222]

Ich hätte gern einen ganzen Quellcode , wenns möglich wäre.
Konzept: Das tragbare Gewicht, die Gewichte der Objekte und dessen Wert sind vorgegeben und stehen noch auf der Form. Ein button zum ak#tivieren und ein Editfeld zur ausgabe...

danke für die schnellen antworten!!!

[Luckie]

Zitat von buff222:

Ich hätte gern einen ganzen Quellcode , wenns möglich wäre.

Hier wird dir niemand deine Hausaufgaben machen. bei konkretne Problemen / Fragen helfen wir dir gerne, aber so nicht.

[Gausi]

Zitat von Luckie:

Man könnte einfach einen BruteForce Algorithmus auf das Problem los lassen und alle Möglichkeiten durchprobieren. Wäre natürlich so ziemlich das uneleganteste was es gibt, dafür aber ziemlich sicher und robust.

Da das Rucksackproblem NP-vollständig ist, bleibt einem nicht wirklich was anderes übrig, wenn man die exakte Lösung haben will. (Ich gehe davon aus, dass bei "alle Möglichkeiten durchprobieren" schon gewisse Abbruchkriterein dabei sind, sodass nicht mehr dazu gepackt wird, wenn der Rucksack eh schon zu schwer ist.)

Man könnte zwar mit diversen Heuristiken rangehen, die evtl. eine Lösung finden, die (beweisbar) nur um einen gewissen Prozentsatz von der richtigen Lösung abweicht, aber das ist hier sicherlich nicht verlangt.

[Phoenix]

Naja. Es gibt da schon Ansätze.

z.B. Packt man ihn erstmal voll. Dann schaut man nach, ob man ein Paket durch ein/zwei/drei... leichtere, die einen höheren Nutzwert haben ersetzen lassen. Aus allen Möglichkeiten nimmt man die mit dem kleinsten Gewicht und dem höchsten Nutzwert aus. Ist Platz für ein neues Paket frei geworden nimmt man das mit dem höchsten Nutzwert das reinpasst. Das ganze so lange, bis nichts mehr geht.

Wenn das nicht mehr geht schaut man, ob sich dann zwei beliebige Pakete durch zwei/drei/vier... leichtere mit höherem Nutzwert ersetzen lassen. Gleiches Prozedere wie oben. Dann mit drei... vier... bis man nichts mehr tauschen kann.

Ist ein zielstrebigeres ausprobieren wobei man viele falsche Lösungen von vorneherein gar nicht probiert bzw. gleich wieder vwerwirft.