Optimierungsproblem |
06.02.2008, 16:08 | 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?! |
|
|
06.02.2008, 18:28 | 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. |
06.02.2008, 19:08 | Auf diesen Beitrag antworten » |
JROppenheimer | Von maximal einmal einladen steht in der Aufgabe nichts 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 |
06.02.2008, 19:33 | 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. |
Anzeige | |
|
|
06.02.2008, 20:41 | 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?! |
06.02.2008, 20:52 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |