[alg] Afmetingen / optimale verpakking 3D

[xilent_xage]

Hoi,

Ik zit al een paardagen op het volgende te broeden:

Ik heb van een aantal pakketten de afmetingen (HxBxD). Pakketten beschouwen we even als legosteentjes: Verschillende afmetingen maar altijd rechthoekig. Ik wil deze pakketten samenvoegen tot 1 groot pakket, met handzame afmetingen. Alle pakketten achter mekaar zou een heel raar lang pakket opleveren, dat moet toch handiger kunnen. Ik wil een samengevoegd pakket hebben waarbij de totale afmetingen zo klein mogelijk zijn.

1. Hoe zouden jullie dit aanpakken? Mijn beste oplossing so far is steeds het pakket zo kantelen dat de kleinste H, B of D op het totaalpakket wordt geplakt aan de kant van de grootste H, B, of D. Maar dat kan vast beter?
2. Ik wil de optimale pakvorm grafisch weergeven als plaatje. Omdat je best wel complexe verpakkingen kan krijgen denk ik dat gewoon ruimtelijk tekenen (evt met per pakketje een andere kleur met legenda) niet gaat werken, omdat je er dan niet binnenin kan kijken. Ik zou natuurlijk ook de blokken transparant maken, of alleen de lijntjes weergeven?

Alvast bedankt voor jullie feedback!

[djluc]

Je kan het in echt 3d doen maar gewoon diverse aanzichten om mee te beginnen is een stuk eenvoudiger. Elke doos een eigen kleur en het is heel duidelijk. Qua plaatsingsalgoritme heb je een aantal slimme methoden of de keuze om brute force te werken. Dus alle mogelijkheden te testen en dan de kleinste te pakken.

Wat handzaam is moet je eigenlijk gewoon vastleggen, dat sluit meteen een oplossing als alles achter elkaar uit.

[Skinny]

Zijn leuke algoritmes... 3d bin packing is het trefwoord waar je naar zoekt. Zelf heb ik veel aan de pagina van David Pisinger gehad :

http://www.diku.dk/hjemmesider/ansatte/pisinger/

voorbeeld implementaties in c :

http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html

de code is niet gedocumenteerd dus veel spit/test en leeswerk maar je leert er veel van