O problema de empacotamento

Numa mudança de casa, enche um caixote atrás do outro e pergunta-se se uma ordem mais inteligente teria precisado de menos. Esse é o problema de empacotamento, e é conhecido por ser difícil: até os computadores só encontram o menor número de caixas para entradas grandes com uma pesquisa engenhosa. Ainda assim, regras simples ficam surpreendentemente perto.

Caixas da mesma altura cheias de objetos coloridos empilhados de tamanhos diferentes, com mais objetos à espera por cima delas
Caixas da mesma altura cheias de objetos coloridos empilhados de tamanhos diferentes, com mais objetos à espera por cima delas

O problema

Dados objetos com tamanhos e caixas que levam todas a mesma quantidade, ponha cada objeto numa caixa sem que nenhuma transborde, usando o menor número possível de caixas. Os tamanhos podem representar pesos, comprimentos, durações ou tamanhos de ficheiros. Parece um passatempo para uma tarde de chuva, mas é NP-difícil: não se conhece nenhum método que encontre rapidamente o menor número de caixas para qualquer entrada.

Regras rápidas

O Next Fit enche uma caixa até o objeto seguinte já não caber, depois começa uma caixa nova e nunca volta atrás. O First Fit mantém todas as caixas abertas e põe cada objeto na primeira caixa com espaço. O Best Fit põe cada objeto na caixa mais cheia que ainda tem espaço. As três decidem logo, o que é útil quando os objetos chegam um a um e têm de ser colocados imediatamente.

Ordenar primeiro

Os objetos grandes são os difíceis, porque precisam de muito espaço livre. Ordenar os objetos do maior para o menor e depois usar o First Fit ou o Best Fit põe os grandes nas caixas enquanto ainda estão vazias, e os pequenos preenchem os espaços. O First Fit Decreasing nunca usa mais de 11/9 do menor número de caixas, mais uma constante, contra 1,7 vezes do First Fit com objetos não ordenados.

Um exemplo

Considere caixas de tamanho 10 e os objetos 2, 3, 2, 1, 3, 4, 5, 6, 7 e 7, que somam 40. O First Fit põe 2, 3, 2 e 1 na primeira caixa e 3 e 4 na segunda, e depois 5, 6, 7 e 7 precisam cada um de uma caixa só para si: 6 caixas. Com os objetos ordenados do maior para o menor, o First Fit Decreasing faz 7 + 3, 7 + 3, 6 + 4 e 5 + 2 + 2 + 1: 4 caixas cheias, o que coincide com o limite inferior de 40 / 10 = 4.

Encontrar o menor número de caixas

Para poucos objetos, a resposta exata pode ser encontrada por programação dinâmica sobre subconjuntos: para cada conjunto de objetos, o menor número de caixas e a última caixa mais vazia que o contêm, construídos a partir dos conjuntos com menos um objeto. Isso leva cerca de 2ⁿ·n passos para n objetos. Instâncias maiores resolvem-se com branch and bound ou programação inteira, e o limite inferior indica quão longe do melhor pode estar um empacotamento.

Onde é usado

Carregar camiões e contentores, cortar tubos ou rolos de papel a partir de comprimentos padrão com o mínimo de desperdício (o problema de corte), distribuir máquinas virtuais por servidores e arrumar ficheiros em discos são todos problemas de empacotamento. Em duas e três dimensões, com caixotes em vez de números, o problema é ainda mais difícil.

Perguntas frequentes

Qual é a diferença entre empacotamento online e offline?

Online, cada objeto tem de ser colocado assim que chega, sem conhecer os restantes; o Next Fit, o First Fit e o Best Fit funcionam assim. Offline, todos os objetos são conhecidos de antemão, por isso podem ser ordenados primeiro, como faz o First Fit Decreasing.

Quão perto do melhor fica o First Fit Decreasing?

Usa no máximo 11/9 do menor número de caixas mais 6/9 de uma caixa, um limite que György Dósa provou ser exato em 2007. Em entradas típicas, costuma ser ótimo ou ficar a uma caixa do ótimo.

O empacotamento é o mesmo que o problema da mochila?

Estão relacionados, mas são diferentes. A mochila enche um só saco com os objetos mais valiosos; o empacotamento põe todos os objetos no menor número possível de sacos. Os métodos exatos de empacotamento funcionam muitas vezes resolvendo, uma e outra vez, problemas parecidos com o da mochila.

Porque é que a aplicação só aceita 12 objetos?

Porque a resposta exata analisa cada conjunto de objetos, e 12 objetos já formam 4096 conjuntos. As regras rápidas aguentariam milhares de objetos, mas o desenho e a comparação com a resposta exata não.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar o empacotamento