Configuração do problema da mochila limitada.Querer:uma lista de todas as embalagens possíveis

Question

Em vez de otimizar qualquer coisa, quero listar todas as embalagens possíveis - inclusive as "incompletas" - da mochila.Claro, eu poderia percorrer todos os subconjuntos do conjunto de objetos e escolher aqueles que satisfazem a restrição de peso (podem ser melhorados colocando um limite superior no tamanho dos subconjuntos para examinar), mas eu realmente gostaria de algo mais eficiente.

Obrigado.

Answer 1

Primeiro classifique seus objetos por peso.Em seguida, arrume a mochila recursivamente.Se o objeto de menor peso ainda não considerado não couber, ou não tivermos nenhum objeto restante, então adicione a mochila atual à nossa lista e retorne, caso contrário, adicione a mochila atual à nossa lista para cada objeto na lista que couber, coloque-o e tente arrumar o resto da mochila com objetos mais pesados ​​que o último objeto que embalamos.

Se pudermos embalar mais de um item de um determinado tipo, substitua menos que por menor ou igual a.

Se tivermos vários objetos com o mesmo peso, precisamos classificar primeiro por peso, depois por alguma ordem arbitrária e usar isso.

 PackKnapsack(knapsack, objects)
   add knapsack to list
   if objects is empty return
   if smallest object does not fit return
   for each object in order from smallest to largest
      if currentobject does not fit
         break
      PackKnapsack(knapsack + currentObject, objects heavier than current object)