 Den Algorithmus finden |
MaxMax
unregistriert
 |
|
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
|
|
25.11.2010 11:59 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
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
|
|
|
26.11.2010 12:36 |
|
|
|
