Progettazione dell'algoritmo: puoi fornire una soluzione al problema dello zaino multiplo?

Question

Sto cercando una soluzione di pseudo-codice su ciò che effettivamente è lo Multiple Knapsack Problem (l'istruzione di ottimizzazione si trova a metà della pagina). I think questo problema è NP Complete quindi la soluzione non deve essere ottimale, piuttosto se è abbastanza efficiente e facilmente implementata sarebbe buona.

Il problema è questo:

• Ho molti elementi di lavoro, con ciascuna un importo diverso (ma determinato e noto) di tempo per completare.
• Devo dividere questi elementi di lavoro in gruppi in modo da avere il numero più piccolo di gruppi (idealmente), con ogni gruppo di elementi di lavoro che non richiede più di una soglia totale - diciamo 1 ora.

Sono flessibile sulla soglia: non deve essere applicata rigidamente, sebbene debba essere chiusa. La mia idea era quella di allocare gli oggetti di lavoro in bidoni in cui ogni bin rappresentava il 90% della soglia, 80%, 70% e così via. Potrei quindi abbinare elementi che prendono il 90% a quelli che prendono il 10% e così via.

Qualche idea migliore?

Answer 1

È necessario http://www.or.deis.unibo.it/knapsack.html, capitolo 6.6 "Problema multiplo di knapscack - algoritmi approssimativi". C'è uno pseudo-codice (stile Pascal) nelle implementazioni di testo e Fortran (sì, è un vecchio libro) come un file ZIP.

Answer 2

Per quanto ne so, il problema è NP completo (Wikipedia confirms), quindi probabilmente non ha molto senso tentare di risolverlo esattamente. Tuttavia, qualsiasi numero di approcci potrebbe essere sufficiente per voi buone: avidi, algoritmi genetici, simulare ricottura ... avido è probabilmente il più facile da implementare:

while (time available in block greater than smallest task duration) 
    find the longest fitting task 
    add it 

... si ottiene l'idea.