Rucksackproblem
-
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ür eure Hilfe
-
Wie meinst du das alle Möglichkeiten durchgehen? Eine Schleife wiederholt grundsätzlich irgendetwas..
-
Ich meine damit das ich jedes Objekt einmal mit jedem kombinieren will bzw auch jedes Objekt solange mit sich selbst zu kombinieren bis die Gewichtsschranke erreicht ist.
-
Was hast du nur mit Gewichten?!
Zeig lieber mal ein wenig Code/Pseudocode her.
-
Höh? Man darf doch jedes Objekt nur einmal einpacken. Du hast eine Menge von Objekten und musst die wertvollste Teilmenge bestimmen, die ein bestimmtes Gewicht nicht überschreitet. In einer Menge gibt es jedes Objekt nur einmal.
-
Nein. In meinem speziellen Problem gibt es eine variable Menge von Produktgruppen, welche jeweils einen Gewinn erzielen und eine Produktionszeit für sich beanspruchen. Ich soll in einer bst Zeit den meisten Gewinn erzielen und darf aus jeder Gruppe beliebig viele Produkte produzieren.
PAP / Pseudocode etc gibt es nicht.
Die Idee ist halt das ich alle möglichen Varianten in einer Schleife durchgehe und so das Optimum suche.
Ich habe dementsprechend bis jetzt eine Klasse Produktgruppen erstellt. Diese hat die Attribute name, produktionszeit, gewinn.
Wird das Programm gestartet kann der Benutzer eine beliebige Anzahl Objekte der Klasse Produktgruppen erstellen und sagen was die maximale Produktionszeit ist
-
Ich weiß net ob ich das richtig verstanden habe, aber wenn dann folgendermaßen:
1. Du rechnest für jede Gruppe "Gewinn durch produktionszeit" und speichst das Ergebinis (z.B in der Variable "Bewertung")
2. nun brauchst du nur noch die Gruppe mit der höchsten bewertung raussuchen und erzeugen
-
Alle Kombinationen direkt durchzugehen dürfte ein bißchen teuer werden. Die Laufzeit ist dann (vermutlich) exponentiell, so dass Du schon mit kleinen Instanzen an die Grenzen Deines Rechners kommst.
Es gibt aber einen Ansatz mit dynamischer Programmierung mit Laufzeit O(n*B), dabei ist n die Anzahl der Elemente und B die Größe des Rucksack. Wenn der Rucksack nicht gerade riesig ist, dann dürfte das noch halbwegs akzeptabel sein. http://de.wikipedia.org/wiki/Rucksackproblem ist ein guter ausganspunkt.
ansonsten gibt's noch jede menge approximationsalgorithmen (und evtl. sogar ein FPTAS?), wenn dir auch eine approximative lösung genügt.
-
DataByte schrieb:
Ich weiß net ob ich das richtig verstanden habe, aber wenn dann folgendermaßen:
1. Du rechnest für jede Gruppe "Gewinn durch produktionszeit" und speichst das Ergebinis (z.B in der Variable "Bewertung")
2. nun brauchst du nur noch die Gruppe mit der höchsten bewertung raussuchen und erzeugen
das reicht nicht. evtl. bleibt ja am schluß noch zeit übrig, in der man noch was anderes produzieren könnte... oder es reicht nicht ganz, aber wenn man von der tollen gruppe eins weniger macht könnte man noch zwei sachen mit etwas niedrigerem gewinn herstellen und so insgesamt trotzdem mehr erreichen.
-
---