Questo è noto come the bin packing problem (che è NP-rigido).
Semplicemente classificare l'ordine decrescente dalle loro dimensioni, e quindi inserendo ogni elemento nel primo scomparto nella lista con spazio rimanente sufficiente, otteniamo 11/9 OPT + 6/9 cassoni (dove OPT è il numero di contenitori utilizzati nella soluzione ottimale). Questo potrebbe facilmente prendere O(n²), o eventualmente O(n log n) con un'implementazione efficiente.
In termini di soluzioni ottimali, non esiste una soluzione di programmazione dinamica che sia nota anche per il problema dello zaino. This resource ha un'opzione - l'idea di base è:
D[{set}] = the minimum number of bags using each of the items in {set}
Then:
D[{set1}] = the minimum of all D[{set1} - {set2}] where set2 fits into 1 bag
and is a subset of set1
L'indice di matrice sopra è letteralmente un set - pensare a questo come una mappa di set di valore, una bitmap o una matrice multidimensionale dove ogni indice è 1 o 0 per indicare se includiamo o meno l'elemento corrispondente a quello dimensionale.
La risorsa collegata considera effettivamente più tipi, che possono verificarsi più volte: ho ricavato la soluzione di cui sopra.
Il tempo di esecuzione dipenderà molto dal numero di articoli che possono essere contenuti in una borsa: sarà O(minimumBagsUsed.2maxItemsPerBag).
Nel caso di 1 borsa, questo è essenzialmente the subset sum problem. Per questo, è possibile considerare il peso come il valore e risolvere utilizzando un algoritmo a zaino, ma questo non funzionerà molto bene per più buste.
Perché no? Considerare gli articoli 5,5,5,9,9,9 con una dimensione di borsa di 16. Se hai appena risolto la somma dei sottoinsiemi, ti rimane 5,5,5 in un sacchetto e 9 in un sacchetto ciascuno (per un totale di 4 borse), invece di 5,9 in ognuna delle 3 borse.
La somma dei sottogruppi/zaino è già un problema difficile: se si utilizza non è in grado di darvi una soluzione ottimale, si può anche usare l'approccio di ordinamento/avidità di cui sopra.
Le borse sono di uguale misura? – JensG
Sì, le borse sono di dimensioni uguali. Vorrà anche sapere come risolvere con borse di dimensioni disuguali. – Jony
Non dovrebbe essere uguale al problema del riempimento della busta "N" con il resto della merce lasciata dopo aver riempito le buste da "1" a "N-1"? Le dimensioni non uguali sono (probabilmente) più difficili. – JensG