Programm zum Ermitteln des kleinsten Körpers

[Josef Friedrich Konrad (Gast)]

Hallo

Folgende Aufgabenstellung:

eine Anzahl von Quadern und Würfeln mit verschiedenen Ausmaßen sollen 
möglichst platzsparend zusammengestellt werden.

Es gibt sicherlich Programme dafür, z.B. in der Logistikbranche. Gibt es 
aber auch was für den Heim bzw Hobbybedarf?

[Röhry (Gast)]

Die machen das anders, das schwere kommt nach unten.

[Jens M. (schuchkleisser)]

Röhry schrieb:
> das schwere kommt nach unten

Müsste das nicht "das schwere kommt nach oben" heißen? ;)

@OP
wozu? Tetris üben?
Es gibt so viele Faktoren die da reinspielen: Gewicht, Tragfähigkeit, 
Entnahmereihenfolge.
Speziell letzteres ist üblicherweise das was zählt.
Kennt der Amateur als "LIFO": Last In First Out.

[●DesIntegrator ●. (Firma: FULL PALATINSK) (desinfector)]

Jens M. schrieb:
> Tetris üben?

oder meinen Lagerraum managen

[georg (Gast)]

● J-A V. schrieb:
> oder meinen Lagerraum managen

Da nützt das am allerwenigsten, da hat Priorität dass man mit möglichst 
wenig Räumaufwand an jede beliebige Schachtel rankommt, und das ist viel 
schwieriger. Und ganz sicher ist es weit entfernt von der dichtesten 
Packung.

Georg

[winzip (Gast)]

Josef Friedrich Konrad schrieb:
> möglichst platzsparend zusammengestellt werden.

Einfach NUR schichten hilft nicht immer. Es ist wie beim Schach: 
entweder verliert man Steine oder hat strategischen Gewinn.

[foobar (Gast)]

Das Problem ist alles andere als trivial.  Zum Einstieg:

https://www.quora.com/What-is-the-bin-packing-problem
https://en.wikipedia.org/wiki/Packing_problems

[c-hater (Gast)]

foobar schrieb:

> Das Problem ist alles andere als trivial.

Das Problem selber ist trivial, ein brute-force-Implementierung dafür 
ist in einer halben Stunde oder so geschrieben und liefert beweisbar die 
optimale Lösung. Nur halt nicht unbedingt heute, oder wenigstens noch 
dieses Jahr...

Nicht trivial ist hingegen, eine gute Näherungslösung für das Problem in 
nicht-exponentieller Zeit zu finden. Inbesondere eine, für die man dann 
auch noch beweisen kann, wieviel weniger gut als die optimale Lösung sie 
im schlimmsten Fall sein wird...

[foobar (Gast)]

> Das Problem selber ist trivial, ein brute-force-Implementierung dafür
> ist in einer halben Stunde oder so geschrieben und liefert beweisbar die
> optimale Lösung.

Nein, eben nicht.  Oder wäre dein Programm auf die obige Lösung für 10 
Quadrate gekommen?  Die Anordnungsmöglichkeiten sind nicht endlich -> 
Brute force klappt nicht.  Bei unterschiedlichen Größen und im 3D wird's 
auch nicht gerade einfacher - vom Beweis des Optimums ganz abgesehen.

[zitter_ned_aso (Gast)]

foobar schrieb:
> die obige Lösung für 10
> Quadrate

Für welche Aufgabenstellung ist diese Lösung? Die 10 Kisten innerhalb 
eines Quadrats so zu plazieren, dass dessen Fläche minimal ist?


Weil platzsparend ist das ja nicht.

3.5 * 3.5 = 12.25 (Flächeneinheiten)

Das kann ich sogar unterbinden wenn ich die Kisten in zwei Reihen 
nebeneinander ablege:

2 * 5 = 10 (Flächeneinheiten)

[foobar (Gast)]

> Für welche Aufgabenstellung ist diese Lösung? Die 10 Kisten innerhalb
eines Quadrats so zu plazieren, dass dessen Fläche minimal ist?

Sorry, nicht genau beschrieben. Ja, es geht um Quadrate im Quadrat, 
hier: kleinste Quadrat, in das 10 gleich große Quadrate passen.

[foobar (Gast)]

Btw:

> 3.5 * 3.5 = 12.25 (Flächeneinheiten)

Es sind eben nicht 3.5 sondern 3+sqrt(0.5)=3.707.. - dadurch wird es mit 
Brute-Force schwierig.

[zitter_ned_aso (Gast)]

foobar schrieb:
> 3+sqrt(0.5)=3.707..

einverstanden ;-)

[Josef Friedrich Konrad (Gast)]

Hey

Hab ein Tool gefunden, als Trial gratis. Nennt sich 3D Load Packer. 
Macht zwar nicht genau das was ich suchte, ist trotzdem eine große Hilfe