Algorithmus: Optimale Kombination von verschiedenen Längen

[Jonelmeier]

Hi,

ich habe eine Frage an alle Algorithmus-Freaks unter euch:

Situation: Ich habe eine Menge verschiedener Längen (von 16cm bis 68cm, Werte können mehrfach auftreten).

Problem: Ich möchte die einzelnen Längen so kombinieren, das ich möglichst viele 100cm Längen bekomme (± 2cm). Es dürfen 2 bis 4 Elemente aus der Grundmenge verwendet werden.

Hintergrund: Es geht um Granitblöcke, aus denen jeweils möglichst genau 100cm lange Treppenstufen zusammengesetzt werden sollen, ohne die Blöcke zu zerschneiden. Auf dem Papier, durch knobeln und ausprobieren existiert bereits eine Lösung, jedoch würde es mich reizen dieses Problem algorithmisch (allgemeiner) zu lösen, u.A. um z.B. die Länge der Stufen oder die Anzahl der zulässigen Blöcke variieren zu können, ohne neu knobeln zu müssen.

Vielleicht kann mir ja jemand einen kleinen Denkanstoß liefern.

Gruß Jonas

[fox67]

Ich würde so beginnen das du dir eine Klasse machst die zwei Variablen enthält Id und Länge. Und dann eine Procedure die mit dem Block mit der Id 1 anfängt und die Länge jedes Blockes einzeln zuder Länge des einen Blockes dazu addiert ergibt es dann bei zwei Blöcken die Länge 100 werden beide Ids in einer Liste gespeichert. Dann wird das selbe gemacht mit block 2 und so weiter zum Schluss wird dann das ergebnis aus der Liste ausgelesen.
Gruß Arni

[bernerbaer]

Algo bei Wikipedia Eindimensionales_Zuschnittproblem oder wikipedia Verschnittplanung

[fox67]

Meine Methode klappt aber nur wenn du die Zahl vorgibst wie viele Blöcke zusammengewürfelt werden können. Deshalb ist sie für dich wahrscheinlich eher unpraktisch

[Jonelmeier]

Der Artikel über das Eindimensionale Zuschnittproblem klingt interessant, leider ist mir die theoretische Definition zu hoch, ich bräuchte eine Pseudo-Implementierung des Algorithmus.

Ich bin noch auf das Behälterproblem gestoßen, welches aber in diesem Fall keine optimalen Ergebnisse liefert:

Code:

Sortiere die Objekte nach absteigendem Länge
Füge die Objekte der Reihe nach ein,
    sodass jedes in den ersten Behälter gegeben wird, in dem noch genug Platz ist.
    Falls in keinem der bereits geöffneten Behälter genügend Platz ist, öffne einen neuen.

Auch die Variante Best Fit Decreasing des Behälterproblems verhält sich ähnlich.

[bernerbaer]

ich habs nicht näher angeschaut aber vielleicht ist ja das etwas:
delphiforfun

[Aphton]

edit: ..