Problema de embalagem descontraída

7

O problema que tenho é como esse problema de empacotamento de lixeira, mas tenho caixas e uma coleção de itens com massas discretas. Eu preciso colocar pelo menos kg de material em cada caixa.nm

Existe uma maneira eficiente de fazer isso? Existe uma maneira de garantir que haja aproximadamente a mesma quantidade em cada compartimento? Ter um bom palpite sobre a distribuição de probabilidade das massas ajuda?

Mais explicitamente:

Eu tenho objetos , cada um tem um tamanho .q{o1...oq}w(oi)N

Preciso encontrar uma coleção de compartimentos separados contendo os objetos para quenB={b1...bn}

biB:obiw(o)>m

por algum . Quando é possível, é isso.m

Lucas
fonte
Qual é a sua medida? Se você pode colocar exatamente (ou pelo menos)mkg de material em cada caixa? Você pode escrever a definição do problema formalmente? Você está familiarizado com o problema da mochila múltipla (que admite um PTAS)?
Gål GD 08/04
Suponho que você queira dizer Medida de eficiência - acho que o mais importante é um tempo de execução esperado? Vou escrever mais formalmente.
Lucas

Respostas:

3

O problema é NP-completo porque está no NP e captura o problema de partição comn=2 e m=12i=1qw(oi)12miniw(oi). Se existir uma partição de peso igual, os itens poderão ser empacotados em dois compartimentos, cada um com peso . Caso contrário, uma das duas caixas teria peso no máximo .12i=1qw(oi)>mm

Sasho Nikolov
fonte
É a minha primeira vez com esse assunto! ASSIM ficar preso em várias coisas. Você conhece algum recurso para ver muitas dessas reduções? Parece bastante estranho a forma como as pessoas pensam nisso!
user6818
O conselho geral é "procure problemas com sons semelhantes". Este foi um caso muito simples, no qual o problema é uma versão mais geral de um problema grave conhecido, portanto, nenhuma transformação real foi necessária. Verifique a referência perguntas cs.stackexchange.com/questions/9556/... e cs.stackexchange.com/questions/11209/... , e qualquer livro de algoritmos, por exemplo, Capítulo 8 aqui: algorithmics.lsi.upc.edu/docs/...
Sasho Nikolov
@ user6818 Você pode estar interessado em nossas perguntas de referência e navegar no site . Além disso, Garey / Johnson!
Raphael