problema di imballaggio

Question

Voglio scrivere una piccola utility di supporto per organizzare la mia collezione digitalizzata audiolibri.

Ho un insieme di cartelle che ho bisogno di scrivere su CD. Le cartelle non può essere divisa. Ogni cartella va su un disco

Voglio riempire i dischi in modo più efficiente:

1. Ridurre al minimo il numero di dischi, e
2. Il numero di dischi parità massimizzare lo spazio disponibile del disco almeno riempito (80 + 20 spazio rimanente è meglio di 50 + 50).

Quali algoritmo devo usare?

Answer 1

Questa è chiamata la Bin Packing Problem ed è NP-difficile, quindi non c'è un semplice algoritmo per risolverlo.

La soluzione che ho trovato ha funzionato meglio (ho fatto un concorso di programmazione con una domanda quasi identico a questo), è stato quello di ordinare le cartelle per dimensione e mettere la cartella più grande che ancora si inserisce sul disco fino a quando è pieno o tutte le cartelle rimanenti sono troppo grande per entrare nello spazio rimanente.

Questo risolve il problema rapidamente, poiché dopo l'ordinamento il resto dell'algoritmo è O (n).

Nel Ran contest ho, ciò ha determinato in 74 dischi invece dei 79 che una soluzione ingenua raggiungerebbe per la nostra più grande insieme di dati di test.

Answer 2

Se si desidera mettere in valigia i file / cartelle su un CD-R del disco, di quanto si potrebbe fare questo in modo ottimale nel tempo pseudo-polinomio. Per fare questo, è necessario dimensioni rotonde di file / cartelle in settori, e contare i settori disponibili su CD-R.

Dopo questo, otteniamo discreto 1-D zaino problema imballaggio , che può essere risolto utilizzando ben programmazione dinamica, con complessità O (n) ,

Per essere più precisi:

• O (n) = O (NO) , causa W è costante nel tuo caso - W è quantità di settori su CD R.
• n quantità di file / cartelle.

Per ottenere migliori prestazioni è possibile ridimensionare sempre over-approssimativa di settori, ad esempio l'installazione:

• dimensione del settore over-approssimata 70K
• ciò che rende 700M / 70k = 10k di tutti i settori su CD-R
• che dovrebbe calcolare in pochi secondi quando i file importo inferiore (1G / 10k = 100k) 100k - n <100'000
• in minuti quando n <10'000'000

Cosa c'è di più:

• soluzione può essere piacevolmente parallelo.

Forse l'applicazione di questo algoritmo in modo greedy "confezionare un cd, in valigia il prossimo cd" farà il proprio lavoro?