Problema de embalagem descontraída

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.$n$$m$

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$$\{o_1...o_q\}$$w(o_i) \in \mathbb{N}$

Preciso encontrar uma coleção de compartimentos separados contendo os objetos para que$n$$B = \{b_1...b_n\}$

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

O problema é NP-completo porque está no NP e captura o problema de partição com$n = 2$ e $m = \frac12 \sum_{i = 1}^q{w(o_i)} - \frac12 \min_{i}w(o_i)$. 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 .$\frac12 \sum_{i = 1}^q{w(o_i)}>m$$m$