Delimitata zaino problema di set-up. Vuoi: un elenco di tutti i possibili imballaggi

Question

Invece di ottimizzare qualsiasi cosa, voglio elencare tutti i possibili - tra cui "incompleta" - imballaggi di zaino. Naturalmente, potrei ciclo attraverso tutti i sottogruppi della serie di oggetti e di scegliere quelli che soddisfano il vincolo di peso (può essere migliorata ponendo un limite superiore alla dimensione dei sottoinsiemi di guardare attraverso), ma mi piacerebbe davvero qualcosa di più efficiente.

Grazie.

Answer 1

Ordina gli oggetti per peso. Poi ricorsivamente confezionare lo zaino. Se l'oggetto più piccolo peso non ancora considerato non va bene, o non abbiamo gli oggetti rimanenti, quindi aggiungere lo zaino corrente alla nostra lista e ritorno, altrimenti aggiungere lo zaino corrente alla nostra lista per ogni oggetto nella lista che si inserisce messo in e cercare di imballare il resto dello zaino con gli oggetti più pesante l'ultimo oggetto abbiamo preparato.

Se siamo in grado di confezionare più di un elemento di un determinato tipo quindi sostituire meno con meno o uguale a.

Se abbiamo più oggetti dello stesso peso dobbiamo ordina primo in peso, poi da qualche ordine arbitrario e utilizzare tale.

 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)