Encaixando matematicamente vários paralelepípedos numa caixa

[Maikon]

Saudações,

Estou com dificuldade na seguinte situação:

1. Tenho um sistema de cálculo de fretes e seguindo o exemplo abaixo adiciono os seguintes produtos ao carrinho de compras:

Produto 01 / medidas (CxLxA): 20x10x10
Produto 02/ medidas (CxLxA): 10x15x30
Produto 03/ medidas (CxLxA): 50x20x10
Produto 04/ medidas (CxLxA): 20x10x20

Tenho a primeira situação, onde há um limite de medidas que o correio aceita, desta forma, faço o seguinte:

Calculo o volume de cada produto, multiplicando as tres medidas e somando.
E calculo o volume das medidas maximas da caixa do correio.

Assim comparo se o volume de minhas caixas é menor que o limite dos correios.

Só que, para realizar o cálculo, eu precisao enviar apenas uma medida, ou seja, uma embalagem, eu faço da seguinte forma:

Pego a maior largura, maior comprimento e somo a altura.
Sei que não está legal, pois fica muito espaço vazio na caixa.

Então eu gostaria de montar uma medida final com base no volume total, desta forma, não entendo como extrair um comprimento, largura e altura do volume total das caixas.

Podem me auxiliar por gentileza neste cálculo?

Agradeço atencipadamente.

[João P. Ferreira]

Boas

pelas minhas contas a caixa do correio teria de ter as medidas da maior caixa

50x20x10

Repara que com estas medidas as outras caixas cabem todas

Produto 01 / medidas (CxLxA): 20x10x10
Produto 02/ medidas (CxLxA): 10x15x30 = 30x15x10
Produto 04/ medidas (CxLxA): 20x10x20 = 20x20x10

Não se esqueça que um cubo pode ser orientado em três direções diferentes.

Cumprimentos

[Maikon]

Bom dia João, grato pela resposta.

Mas são caixas de produtos, logo estão cheias.

Desta forma, vou ter que ter uma embalagem que abrigue as outras também.

[João P. Ferreira]

Mas as medidas que nos dá, são as medidas das caixas ou as medidas do produto?

Está um pouco confuso o problema...
vc quer uma caixa que otimize espaço por forma a que caibam todos os produtos lá dentro?
Tipo puzzle..?!

[Maikon]

Olá, grato pela atenção.

Meu problema é o seguinte:

1. Eu tenho um carrinho de compras, com varios produtos, produtos de medidas diferentes.

2. Preciso calcular o frete destes produtos, só que, os correios me pede: Comprimento x Largura x Altura

Ou seja, se eu somar as alturas, estaria empilhando as caixas, só que, eu poderia encaixar produtos do lado, otimizando o espaço.

Então pensei em calcular o volume dos produtos, só que não sei se consigo transformar este volume nas dimensoes que preciso enviar para o sistema calcular o frete.

Veja se fui claro, estou confuso, hehe... obrigado.

[João P. Ferreira]

E quantos Produto 01, Produto 02, Produto 03, Produto 04 tem de cada?

É só um de cada, ou pode ter várias combinações

Exemplo: 4 unidades do Produto 01, 9 unidades do Produto 02, 2 unidades do Produto 03, 7 unidades do Produto 04.

Ou melhor, os produtos têm todos o mesmo número de unidades?

[Maikon]

Pode ter vários.

É um carrinho de compras de loja virtual, o cliente pode comprar N produtos e cada produto tem uma medida e cada produto pode ter mais de 1, pode ter N também.

[João P. Ferreira]

Meu caro

Você está perante um problema de otimização de espaço 3D e ainda por cima estocástico, pois nem sabe deterministicamente quais os produtos que quer colocar na caixa.

Repare antes de tudo, que não basta somar volumes.
Imagine para o caso 2D, que quer arranjar o melhor retângulo, para encaixar dois retângulos diferentes.
A área do retângulo solução é sempre maior que a soma das áreas dos retângulos que se quer encaixar. (vede anexo)

O problema é estocástico, pois vc nem sabe as quantidades de cada produto no mesmo frete.
Considerei uma distribuição uniforme, i.e. o mesmo número de produtos 1,2,3,4.

O problema que coloca de otimização é complexo, mas para esse caso particular com as medidas que referiu, achei a caixa do correio com as medidas:

50x25x20

Pareceu-me ser esta a caixa com volume mínimo, onde você consegue encaixar todos os 4 produtos. Vede desenho anexo.

Mas repare que se se concluir estatisticamente que são vendidos muitos mais produtos 1 do que produtos 3, a solução pode ser outra.

A solução que apresentei é para um frete com 4 produtos diferentes.

Por certo haverão outras soluções, não digo de todo que esta seja única

Cumprimentos

Anexos

[Maikon]

João, fantástica sua sugestão.

Agradeço bastante sua atenção e empenho em me ajudar, estava totalmente no escuro quanto a solução, e com base na sua idéia vou aplicar uma lógica na programação!

Obrigado mesmo!