Den Algorithmus finden |
| 25.11.2010, 11:59 | Auf diesen Beitrag antworten » |
| MaxMax | Den Algorithmus finden Meine Frage: Hallo Liebe Leute, ich sitze vor einer Aufgabe die ich leider nicht so einfach lösen kann. Es geht um folgende Überlegung: Ein Behälter mit einem begrenztem Volumen soll mit Bausteinen befüllt werden. Jeder Baustein hat seine eigene Nummer, die nicht doppelt vorkommt. Die Steine haben verschiedene Volumen, wobei auch gleichgroße Bausteine vorkommen können. Unabhängig vom Volumen haben diese Bausteine auch verschieden Gewichte, hier kann es auch gleich-schwere Bausteine geben. Jetzt ist die Fragen wie viele Möglichkeiten gibt es den Behälter zu befüllen? Oder gibt es einen Algorithmus, der die Anzahl der Möglichkeiten beschreibt. Die Aufgabe ist es die Steine herauszusuchen, die den Behälter so voll machen, dass ein Maximalgewicht rauskommt. Dabei sei das Maximalgewicht im Vordergrund (z.b. Behälter kann auch nur halbvoll gemacht werden wenn es dabei zum Maximalgewicht kommt). Ein Beispiel mit quadratischer Fläche des Behälters und der Bausteine: Behälter: Fläche: 1m x 1m = 1m² ; die Höhe: 15m Höhe und Gewicht der Bausteine (Fläche: 1m x 1m): A: 3m und 4kg B: 5m und 6kg C: 2m und 4kg D: 4m und 2kg E: 6m und 5kg F: 4m und 3kg G: 2m und 4kg Nach meinem Ausprobieren komme ich auf die beste Kombination: B, C, E, G mit 15m Höhe und 19kg Maximalgewicht Das ist aber einfach, denn bei meiner Aufgabe gibt es über 50 Bausteine. Hat jemand von euch eine Idee, oder gar eine Lösung des Problems? Viele Grüße Meine Ideen: Lösen durch Ausprobieren war jetzt meine einzige Lösung |
|
|
|
| 26.11.2010, 12:36 | Auf diesen Beitrag antworten » |
| ed209 | Hi Das Problem ist eine Variante des Rucksackproblems: http://de.wikipedia.org/wiki/Rucksackproblem (Beachte, daß das Gewicht bei deiner Aufabe eine andere Rolle spielt als bei dem "original" Rucksackproblem). Niemand kennt eine Lösung bei der man nicht ausprobieren muß, wohl aber gibt es Heuristiken die effizienter Ausprobieren 
Gruß, ED |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
