Problema: Dato un elenco L di oggetti di dimensioni possibili dal set S = {1,2,4,8} e fornitura illimitata di contenitori di dimensioni 16 ciascuno e dobbiamo usare il minimo possibile numeri di contenitori per imballare tutti gli oggetti di L.
Sto anche cercando una soluzione ottimale (o quasi ottimale) usando la programmazione dinamica o altrimenti nei seguenti scenari quando
- L non viene fornito offline, ma ci viene chiesto di adattare gli oggetti uno alla volta senza conoscere le richieste future (imballaggio del contenitore in linea in 1-D).
- le dimensioni possono essere da SXS e i contenitori sono di capacità (16,16) ciascuno. (Imballaggio bidone vettoriale).
Presupposto: imballaggio ottimale significa il miglior imballaggio possibile da tutti gli imballaggi possibili, ovvero l'imballaggio con il numero minimo di contenitori utilizzati.
L'imballaggio del contenitore vettoriale effettivamente generalizzato è NP-hard, ma penso che le dimensioni standard dovute da un insieme finito, soluzioni più efficienti e migliori possano esistere.
Il mio approccio: Chiaramente, la modalità offline 1-D può essere compresso in < = optimum + 1 utilizzando l'intelligente associazione di oggetti.
Ma sono bloccato per gli altri 2 aspetti sopra indicati.
Conosco gli algoritmi di First Fit, Best Fit, First Fit Decreasing ma sto cercando questa soluzione specifica per il problema.