- Oggetto in corso
- Entra
- Non entra
Problema del bin packing
Scatole nei furgoni, file sui dischi, lavori sulle macchine: il problema del bin packing chiede come sistemare una lista di oggetti nel minor numero possibile di contenitori uguali. Non si conosce nessun metodo veloce che trovi sempre la sistemazione migliore, ma alcune regole semplici ci vanno vicino. Scegli una regola, seguila passo dopo passo e confrontala con la risposta esatta. Tocca un oggetto sullo scaffale, poi tocca un contenitore per metterlo dentro: i contenitori verdi hanno posto per l'oggetto, e Nuovo contenitore ne apre un altro. Tocca un oggetto in un contenitore per toglierlo di nuovo. Sistema tutti gli oggetti in meno contenitori che puoi; il limite inferiore (il peso totale diviso per la dimensione dei contenitori, arrotondato per eccesso) e il minimo possibile mostrano quanto ci sei vicino, e Minimo di contenitori mostra la sistemazione migliore. Cambia i pesi degli oggetti (in chilogrammi) e la dimensione dei contenitori nel pannello. La vista Passo passo mostra come sistemano gli oggetti le regole veloci: Next Fit, First Fit o Best Fit, sugli oggetti nell'ordine inserito o ordinati dal più grande, oppure la risposta esatta trovata dalla programmazione dinamica. Premi Avvia per guardare gli oggetti entrare nei contenitori, oppure Passo e Indietro per procedere un passo alla volta, e trascina il cursore dei passi per saltare dove vuoi. Con l'area di gioco selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Tocca un oggetto, poi un contenitore con spazio per metterlo dentro, oppure Nuovo contenitore per aprirne un altro.
- Prova a usare meno contenitori possibile, oppure premi Minimo di contenitori per vedere l'impacchettamento migliore.
- Apri la vista Passo passo, scegli una regola e premi Avvia per vedere ogni oggetto provare i contenitori.
Le regole
Next Fit tiene aperto solo l'ultimo contenitore: un oggetto che non ci entra inizia un nuovo contenitore. First Fit prova i contenitori a partire dal primo e prende il primo con spazio sufficiente. Best Fit prova tutti i contenitori e prende il più pieno con spazio sufficiente, lasciando inutilizzato meno spazio possibile. First Fit e Best Fit possono anche ordinare prima gli oggetti dal più grande al più piccolo: così si ottengono First Fit Decreasing e Best Fit Decreasing.
La risposta esatta
L'ultima regola non è una regola empirica: trova il minor numero di contenitori con la programmazione dinamica sugli insiemi di oggetti. Per ogni insieme di oggetti tiene il minor numero di contenitori che li contengono e, tra le sistemazioni con quel numero di contenitori, il carico più piccolo nell'ultimo contenitore. Un insieme cresce di un oggetto alla volta, che riempie un po' di più l'ultimo contenitore oppure ne apre uno nuovo. Con n oggetti ci sono 2ⁿ insiemi, ed è per questo che l'app accetta al massimo 12 oggetti. Il limite inferiore, cioè la dimensione totale divisa per la dimensione dei contenitori e arrotondata per eccesso, mostra quanto una sistemazione è vicina alla migliore.
Domande frequenti
Qual è la regola migliore per il bin packing?
Tra le regole veloci, First Fit Decreasing e Best Fit Decreasing sono le più forti: non usano mai più di 11/9 del numero minimo di contenitori, più una piccola costante. First Fit e Best Fit su oggetti non ordinati restano entro 1,7 volte il numero minimo di contenitori, e Next Fit entro 2 volte.
Perché il bin packing è difficile?
Decidere se gli oggetti entrano in soli due contenitori è già il problema della partizione, che è NP-completo. Quindi, a meno che P = NP, nessun metodo trova velocemente il minor numero di contenitori per ogni input, e i metodi esatti richiedono tempo esponenziale nel caso peggiore.
Che cos'è il limite inferiore?
La dimensione totale degli oggetti divisa per la dimensione dei contenitori, arrotondata per eccesso. Nessuna sistemazione può usare meno contenitori, perché i contenitori devono contenere tutti gli oggetti. Spesso la sistemazione migliore lo raggiunge, ma non sempre: tre oggetti di dimensione 6 con contenitori da 10 hanno un limite inferiore di 2 e richiedono 3 contenitori.
È programmazione dinamica?
La risposta esatta sì: costruisce la sistemazione migliore per ogni insieme di oggetti a partire dalle sistemazioni migliori di insiemi più piccoli. Le regole veloci sono metodi greedy, che decidono una volta e non tornano mai indietro.
Viene inviato qualcosa da qualche parte?
No. Tutto viene calcolato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor