Caixas usadas
Limite inferior
Mínimo possível

      Pesos dos objetos (kg)

        Mais sobre o problema de empacotamento

        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

        1. Toque num item e depois numa caixa com espaço para o pôr lá, ou em Nova caixa para abrir outra.
        2. Tente usar o menor número de caixas, ou prima Mínimo de caixas para ver a melhor arrumação.
        3. 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