Karton Problem

Freizeit & Hobby Rätsel
#1

Hallo,

im Brett VB hat vor ein paar Monaten Jemand nach einer Lösung für ein Problem gefragt, das mich seit dem nicht mehr los lässt.

Ein Programm soll ermitteln, wie man in einen Karton so viel wie möglich kleine Schachteln bekommt.
Angegeben werden die Innenmasse des Kartons und die Außenmaße der Schachtel, es kommen immer mehrere Schachteln mit der selben Abmessung in einen Karton.

Meine Überlegungen bisher:

Ich habe für jede der Schachteln sechs verschiedene Möglichkeiten sie in den Karton zu legen.
Dabei gibt es drei verschiedene Abmessungen, wie der Karton damit ausgefüllt wird. Ich müsste, um alle Kombinationen zu berechnen jede Richtung in drei Teile teilen, den Karton also in 3 hoch 3 = 27 Teile aufteilen und bekomme damit 6 hoch 27 Kombinationen, für die das Optimum ermittelt werden muss, in jedem der 27 Bereiche können ja immer Null bis ‚ganzzahliger Anteil von (Karton-Abmessung/Schachtel-Abmessung)‘ Schachteln liegen.

Das alles durchrechnen und am Ende den höchsten Wert nehmen dauert auch mit einem modernen Rechner ewig, das muss doch schneller gehen? Aber wie?

Hier wurden schon schwerere Rätsel gelöst, denke ich. :smile:

Gruß, Rainer

#2

Hallo,

im Brett VB hat vor ein paar Monaten Jemand nach einer Lösung
für ein Problem gefragt, das mich seit dem nicht mehr los
lässt.

Ein Programm soll ermitteln, wie man in einen Karton so viel
wie möglich kleine Schachteln bekommt.
Angegeben werden die Innenmasse des Kartons und die Außenmaße
der Schachtel, es kommen immer mehrere Schachteln mit der
selben Abmessung in einen Karton.

Das ist eine Abwandlung des „dreidimensionalen Rucksackproblems“ in der Informatik, und ist alles andere als trivial. Wenn du ein bisschen danach suchst, wird dir schnell klar, was ich meine. Und ich denke, dass das Informatikbrett passender wäre :wink:

Für viele Anwendungen nimmt man iterative Algorithmen, die nicht garantiert die beste Lösung ergeben, aber in den meisten Fällen gute Lösungen in akzeptabler Zeit.

[…]

Hier wurden schon schwerere Rätsel gelöst, denke ich. :smile:

Sicher? vermutlich nicht allzu viele :wink:

Grüße,
Moritz

#3

Hallo Moritz,

Das ist eine Abwandlung des „dreidimensionalen
Rucksackproblems“ in der Informatik,

ahhh, danach werde ich gleich mal googeln.

und ist alles andere als trivial.

*gg* Dann bin ich ja zufrieden. Ich dachte schon ich wäre einfach nur zu dämlich. :smile:

Wenn du ein bisschen danach suchst, wird dir schnell
klar, was ich meine. Und ich denke, dass das Informatikbrett
passender wäre :wink:

Darauf bin ich nicht gekommen. Mir waren hier im Brett Lösungen aufgefallen, die einfach genial waren. Deshalb habe ich gedacht, wo soll das lösbar sein, wenn nicht hier. Du hast mir ja auch einen Tipp gegeben, so falsch war es dann doch nicht. :smile:

Für viele Anwendungen nimmt man iterative Algorithmen, die
nicht garantiert die beste Lösung ergeben, aber in den meisten
Fällen gute Lösungen in akzeptabler Zeit.

[…]

Hier wurden schon schwerere Rätsel gelöst, denke ich. :smile:

Sicher? vermutlich nicht allzu viele :wink:

Ein paar aber schon, die Rätsel müssen eine solche Lösung ja auch fordern. Wenn ich schlauer wäre, würde ich mir mal eins ausdenken … :smile:

Danke für den Tipp!

Gruß, Rainer

#4

Hi!

Also ich hätte da ein Programm, dass das Problem lösen kann. Eine Excel-Anwendung, die ich vor ein paar Jahren mal geschreiben habe. Eigentlich ist die Anwendung für eine lineare Optimierung von Unternehmen gedacht. Aber das Karton-Problem ist damit auch lösbar. Mathematsich gesehen aber nur als Annährung am Optimum. Außerdem würde das Programm im jetztigen Zustand nur anzeigen wieviele Schachtel im Karton passen, und wieviele Schachtel hochkant, quer usw. dann im Karton sind. Allerdings nicht wie die genau gepackt werden. Könnte man aber ja vielleicht noch hinbekommen.

Intresse?

MfG

Hartmut Börger

#5

Hallo,

Intresse?

Ja, natürlich! Das ist die Beste Option von allen, da kann ich den Code lesen und verändern. :smile:

Gruß, Rainer