Estou procurando uma solução de pseudo-código para o que é efetivamente oProblema de Mochila Múltipla (a declaração de otimização está na metade da página). Eupensar esse problema é NP Complete, portanto, a solução não precisa ser ideal, se for razoavelmente eficiente e facilmente implementável, isso seria bom.

O problema é este:

Tenho muitos itens de trabalho, cada um com um tempo diferente (mas fixo e conhecido) de tempo para concluir.Eu preciso dividir esses itens de trabalho em grupos para ter o menor número de grupos (idealmente), com cada grupo de itens de trabalho não demorando mais que um determinado limite total - digamos 1 hora.

Sou flexível quanto ao limite - ele não precisa ser aplicado rigidamente, mas deve estar próximo. Minha idéia era alocar itens de trabalho i, não em posições em que cada posição representa 90% do limite, 80%, 70% e assim por diante. Eu poderia então combinar itens com 90% a 10%, e assim por diante.

Alguma ideia melhor?