Optimierungsproblem

Neue Frage »

Auf diesen Beitrag antworten »
JROppenheimer Optimierungsproblem

Gegeben ist:

Ladungskapazität T
Waren 1...n
Gewicht i zur Ware i
Wert i zur Ware i
und es ist erlaubt einen bruchteil epsilon i der Ware i zu laden
mit 0 <= epsilon i <= 1

Jetzt soll ich einen GreedyAlg schreiben, der die LAdungskapazität maximal ausschöpft und gleichzeitig den Wert der Ladung maximiert.

Ich bin hier nicht sicher ob ich das dynamisch machen soll ... denn normalerweise schreiben die das dazu in den Übungen.

Ich hätte mir das jetzt so gedacht:

Eine Ware i hat einen Wert, und man kann einen bestimmten Teil dieser Ware einladen. Das heisst, man kann von vornherein die Ware in eben diese Anzahl von Unterwaren einteilen. Die ANzahl dieser lässt sich ja leicht berechnen.
Jeder dieser Unterwaren hat ja auch einen Wert.
Jetzt hätte ich gesagt, wichtig ist, der Faktor: Wert_der_Unterware : Gewicht_der_Unterware ... sei das mal alpha_i

Jetzt würd ich sagen, man sortiert die Waren nach eben diesem Faktor absteigend. Das heisst, die Waren zuerst, bei denen der Faktor alpha_i am größten ist. Die lädt man solange ein, bis grob: der Laster voll ist .... dann müsste der Wert der Ware maximal sein....

was denkt ihr?!
 
Auf diesen Beitrag antworten »
Tobias

Diese Aufgabe kommt mir -wie du sie beschreibst- schon spanisch vor. Wie du sagst, lädt man einfach die Ware mit dem größten Wert/Gewicht - Quotienten.

Edit: Jetzt versteh ichs gerade schon ein bisschen besser: Du darfst jede Ware maximal einmal einladen nehme ich an? Wert/Gewicht scheint die richtige Greedy-Gewichtungsfunktion zu sein.
Auf diesen Beitrag antworten »
JROppenheimer

Von maximal einmal einladen steht in der Aufgabe nichts großes Grinsen

Aber ich gehe mal davon aus, dass ich die Ware beliebig einladen kann ...

Das mit den Aufgabenstellungen ist ja immer so ne Sache. Wenn ich von jeder Ware unendlich viel habe, dann ist das Problem ja schnell gelöst. Dann nimmt man einfach nur die, wo Wert/Gewicht maximal ist, aber angenommen ich habe eben diese Ware_i nur "einmal" das heisst wenn ich die in FünftelBruchteile einladen kann, dass ich dann nur 5 dieser FünftelBruchteile habe, dann sieht es doch schon wieder anders aus ... aber ich meine mit dem wertProTeil/gewichtProTeil Faktor müsste das sogar stimmen ... ich bastel noch mal kurz dran, wenn ichs hab inkl beweis poste ich das mal

sorry, wenn meine ausführungen etwas nach kauderwelch klingen
Auf diesen Beitrag antworten »
Tobias

Das Problem ist als KNAPSACK oder Rucksackproblem bekannt.
http://de.wikipedia.org/wiki/Rucksackproblem

Die Schwierigkeit des Problems wird nun bei euch drastisch reduziert, weil man auch Teile einer Ware einpacken darf. Das macht dann die Verwendung von Greedy-Strategien möglich: Packe die wertvollsten Teile der Reihe nach ein und stückel evt. den letzten Gegenstand, um einen maximalen Füllstand zu erhalten.

Bei Aufgaben, die so trivial aussehen, bin ich immer skeptisch, nicht was übersehen zu haben. Augenzwinkern
 
Auf diesen Beitrag antworten »
JROppenheimer

Aber soweit ich das einsehn kann, nicht nur die wertvollsten, sondern die wertvollsten teilWaren, deswegen sag ich ja, wert pro gewicht für jede teilware ausrechnen. dann bin ich sicher, dass ich den platz, den ich nutze OPTIMAL nutze. was denskt Du?!
Auf diesen Beitrag antworten »
Tobias

Ja, natürlich ist die Bemessensgrundlage der Wert eines Teils pro Gewichtseinheit. Das genau gibt der Quotient Wert/Gewicht an.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »