Configuração do problema da mochila limitada.Querer:uma lista de todas as embalagens possíveis
-
28-09-2019 - |
Pergunta
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.
Solução
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)