- Objeto a ser arrumado
- Cabe
- Não cabe
Problema de empacotamento (bin packing)
Caixotes em carrinhas, ficheiros em discos, tarefas em máquinas: o problema de empacotamento, ou bin packing, pergunta como arrumar uma lista de objetos no menor número possível de caixas iguais. Não se conhece nenhum método rápido que encontre sempre o melhor empacotamento, mas regras simples ficam perto. Escolha uma regra, siga-a passo a passo e compare com a resposta exata. Toque num objeto da prateleira e depois toque numa caixa para o pôr lá dentro: as caixas verdes têm espaço para ele, e Nova caixa abre outra. Toque num objeto dentro de uma caixa para o voltar a tirar. Arrume todos os objetos no menor número de caixas que conseguir; o limite inferior (o peso total dividido pelo tamanho da caixa, arredondado para cima) e o mínimo possível mostram quão perto está, e Mínimo de caixas mostra a melhor arrumação. Altere os pesos dos objetos (em quilogramas) e o tamanho das caixas no painel. A vista Passo a passo mostra como as regras rápidas arrumam: Next Fit, First Fit ou Best Fit, com os objetos pela ordem introduzida ou ordenados do maior para o menor, ou a resposta exata encontrada pela programação dinâmica. Prima Reproduzir para ver os objetos entrarem nas caixas, ou Avançar e Recuar para ir um passo de cada vez, e arraste o controlo de passos para saltar para qualquer ponto. Com o tabuleiro selecionado, as setas avançam passo a passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e para o fim.
Como funciona
- Toque num item e depois numa caixa com espaço para o pôr lá, ou em Nova caixa para abrir outra.
- Tente usar o menor número de caixas, ou prima Mínimo de caixas para ver a melhor arrumação.
- Abra a vista Passo a passo, escolha uma regra e prima Reproduzir para ver cada item experimentar as caixas.
As regras
O Next Fit só mantém aberta a última caixa: um objeto que não cabe nela começa uma caixa nova. O First Fit experimenta as caixas a partir da primeira e escolhe a primeira com espaço. O Best Fit experimenta todas as caixas e escolhe a mais cheia com espaço, deixando o mínimo de espaço por usar. O First Fit e o Best Fit também podem ordenar primeiro os objetos do maior para o menor, o que dá o First Fit Decreasing e o Best Fit Decreasing.
A resposta exata
A última regra não é uma regra prática aproximada: encontra o menor número de caixas por programação dinâmica sobre os conjuntos de objetos. Para cada conjunto de objetos, guarda o menor número de caixas que os contêm e, entre os empacotamentos com esse número de caixas, a menor carga na última caixa. Um conjunto cresce um objeto de cada vez, que ou completa a última caixa ou abre uma nova. Com n objetos há 2ⁿ conjuntos, e é por isso que a aplicação aceita no máximo 12 objetos. O limite inferior, ou seja, o tamanho total dividido pelo tamanho das caixas e arredondado para cima, mostra quão perto do melhor está um empacotamento.
Perguntas frequentes
Qual é a melhor regra de empacotamento?
Das regras rápidas, o First Fit Decreasing e o Best Fit Decreasing são as mais fortes: nunca usam mais de 11/9 do menor número de caixas, mais uma pequena constante. O First Fit e o Best Fit com objetos não ordenados ficam dentro de 1,7 vezes o menor número de caixas, e o Next Fit dentro de 2 vezes.
Porque é que o empacotamento é difícil?
Decidir se os objetos cabem em apenas duas caixas já é o problema da partição, que é NP-completo. Por isso, a não ser que P = NP, nenhum método encontra rapidamente o menor número de caixas para qualquer entrada, e os métodos exatos demoram um tempo exponencial no pior caso.
O que é o limite inferior?
O tamanho total dos objetos dividido pelo tamanho das caixas, arredondado para cima. Nenhum empacotamento pode usar menos caixas, porque as caixas têm de conter todos os objetos. Muitas vezes o melhor empacotamento atinge-o, mas nem sempre: três objetos de tamanho 6 com caixas de 10 têm um limite inferior de 2 e precisam de 3 caixas.
Isto é programação dinâmica?
A resposta exata é: constrói o melhor empacotamento de cada conjunto de objetos a partir dos melhores empacotamentos de conjuntos mais pequenos. As regras rápidas são métodos gulosos, que decidem uma vez e nunca voltam atrás.
É enviado algum dado para algum lado?
Não. Tudo é calculado no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor