Il problema dello zaino
Il problema dello zaino (o “knapsack problem”) è un classico problema di ottimizzazione combinatoria. In una versione semplificata del problema, hai un insieme di oggetti, ognuno con un peso e un valore, e un sacco con una capacità massima. L’obiettivo è determinare il numero di ogni oggetto da includere nel sacco in modo da massimizzare il valore totale senza superare la capacità del sacco.
Il problema del bin packing
Il problema del bin packing (conosciuto in italiano come problema dell’imballaggio nei contenitori) è un classico problema combinatorio. Si tratta di un problema di ottimizzazione che si può descrivere così:
Definizione del problema:
Dati:
- Un insieme di oggetti, ciascuno con un peso.
- Un numero infinito (o limitato) di contenitori, ciascuno con una capacità massima.
Obiettivo:
- Minimizzare il numero di contenitori utilizzati per “imballare” tutti gli oggetti senza superare la capacità di ciascun contenitore.
Tipologie del problema:
- Bin packing classico: tutti gli oggetti devono essere inseriti nei contenitori.
- Bin packing online: gli oggetti arrivano uno alla volta e devono essere posizionati immediatamente.
- Bin packing multi-dimensionale: gli oggetti hanno dimensioni multiple (es. larghezza, altezza, profondità).
- Bin packing con vincoli: aggiunte condizioni extra, come priorità o raggruppamento.
Soluzioni algoritmiche:
1. Algoritmi Greedy (euristici)
Gli algoritmi greedy cercano di trovare soluzioni veloci, ma non necessariamente ottime:
- First-Fit (FF): Inserisci ogni oggetto nel primo contenitore che ha spazio sufficiente.
- Best-Fit (BF): Inserisci ogni oggetto nel contenitore che lascia meno spazio libero dopo l’inserimento.
- Worst-Fit (WF): Inserisci ogni oggetto nel contenitore che lascia più spazio libero dopo l’inserimento.
Esempio di algoritmo First-Fit:
- Ordina gli oggetti in ordine non specifico (o per grandezza decrescente se vuoi ottimizzare di più).
- Prendi ogni oggetto e mettilo nel primo contenitore con spazio sufficiente.
- Se nessun contenitore ha spazio, aprine uno nuovo.