Matematické Fórum

Ahoj,
1. součet stran nejvetšího balíku nesmí přesáhnout 150cm, což znamená, ano, protože by se v tu chvíli vešel do toho balíku pouze jeden balík, když budu ignorovat tloušťku stran vnějšího balíku, což si v rámci tolerance můžeme dovolit.
2. Teoreticky ano, ale pro zjednodušení výpočtu bych toto vyloučil.
Díky

Ahoj,
"zda se počet balíků s různými velikostmi vejde do rozměru konkrétního velkého balíku o daném maximálním rozměru"

Aby se všechny vkládané balíky vešly do jednoho velkého balíku (dále krabice), zjevně musí platit (nutná podmínka), že  součet jejich objemů není větší než objem krabice, do které je mám vložit.

Zkusím speciální případy, kdy si myslím, že lze zaskládat balíky do krabice "bez mezer", tj. objem všech balíků je roven objemu krabice:

1. Mám krychlovou krabici 8x8x8, tedy 512 objemových jednotek.
Stanovím si podmínku, že vkládané balíky jsou rovněž krychle. Jejich povolené velikosti jsou pouze 1x1x1, 2x2x2, 4x4x4.
Krychlí s délkou hrany  je a, krychlí s délkou hrany 2 je b, krychlí s délkou hrany 4 je c.
Potom tvrdím, že všechny balíky se vejdou (dají se naskládat) do krabice právě tehdy, když

[mathjax]a+8*b+64*c=512[/mathjax]

Pro krabici 120x120x120 cm by přípustné velikosti balíků byly krychle o hraně 60, 30, 15 cm.
(Rovnice  se dá zobecnit na libovolné další půlení délky hrany, 7,5 cm atd.)
Balíky mohu ukládat např. od největších k nejmenším tak, že když mi větší balíky dojdou, z 8 menších balíků seskládám 1 větší balík, který uložím na následující pozici většího balíku.

2. Krychlová krabice 120x120x120 cm.
Vkládané balíky budou hranoly s podstavou velikostí kreslicích čtvrtek: A4(30x20), A3(40x30), A2(60x40), a jednotnou výškou,(která dělí 120), např 10. Když budeme balíky pokládat na dno krabice podstavou dolů, bude rovnice pro úplné pokrytí  jedné vrstvy balíků v krabici

[mathjax]a+2*b+4*c=24[/mathjax]

kde a je počet balíků velikosti A4, b je počet balíků velikosti A3, c je počet balíků velikosti A2. Rovnice pro naplnění celé krabice bude mít pravou stranu násobenou počtem vrstev, v případě jednotné výšky balíku 10 cm to bude

[mathjax]a+2*b+4*c=24*12[/mathjax]

------------------------------------------------------------------------------------------------------------------
Vstupní hromadu balíků roztřídím na tři hromádky podle velikosti, spočítám je a dosadím  za a,b,c. Když mi vyjde levá strana  menší než pravá, zbyde mi v bedně místo, v případě rovnosti bude bedna zaplněna bez mezer, jinak se balíky do bedny nevejdou.

↑ lracek:
Ahoj, jak definuješ, že jeden balíček je větší než jiný?
Co myslím tím pojmem "volné krychle prostoru"?

Ale to co uvádíš bude nejspíš nějaká aproximace optimálního řešní (hladový algoritmus). O takových jde často určit odhad o kolik nejvíce se mohou lišit od optimálního řešení. A možná ani nebude existovat polynomiální optimalizační algoritmus...