Problema acotada mochila puesta a punto. Desear: una lista de todos los posibles envases

Question

En lugar de optimizar la nada, quiero una lista de todos los posibles - incluyendo "incompleta" - envases de la mochila. Por supuesto, podría bucle a través de todos los subconjuntos del conjunto de los objetos y escoger los que satisfacen la restricción de peso (se pueden mejorar mediante la colocación de un límite superior en el tamaño de los subconjuntos de mirar a través), pero realmente me gustaría algo más eficiente.

Gracias.

Answer 1

primero ordenar sus objetos, en peso. Luego empaque de forma recursiva la mochila. Si el objeto de peso más pequeño aún no se considera no se ajusta, o tenemos ningún objeto restante, a continuación, añadir la mochila actual a nuestra lista y vuelta, de lo contrario añadir la mochila actual a nuestra lista para cada objeto en la lista que encaja ponen en y tratar de empacar el resto de la mochila con objetos pesados ??que el último objeto que nos llena.

Si podemos embalar más de un elemento de un tipo dado luego vuelva a menos que con menor o igual a.

Si tenemos varios objetos del mismo peso que hay que solucionar primero en peso, y luego por un poco de orden arbitrario, y el uso que.

 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)