nello zaino
Peso
Massimo possibile

    Oggetti

      Di più sul problema dello zaino

      Problema dello zaino

      Puoi portare solo un certo peso, e ogni oggetto ha un peso e un valore. Quali oggetti prendi per portare il valore più alto? Provare ogni combinazione raddoppia il lavoro a ogni oggetto. Una tabella con gli oggetti sulle righe e le capacità sulle colonne trova lo zaino migliore una cella alla volta. Tocca un oggetto per metterlo nello zaino e toccalo di nuovo (nello zaino o sullo scaffale) per toglierlo. Lo zaino si riempie in base al peso, e i riquadri mostrano i dollari che hai messo nello zaino rispetto al massimo possibile. Premi Carico migliore per vedere lo zaino migliore. Nel pannello puoi cambiare i chili e i dollari degli oggetti, aggiungere o rimuovere oggetti e impostare la capacità dello zaino. La vista Tabella mostra come la programmazione dinamica trova lo zaino migliore: premi Avvia per guardare la tabella che si riempie, oppure Passo e Indietro per procedere un passo alla volta, e trascina il cursore dei passi per saltare dove vuoi. Ogni riga aggiunge un oggetto, ogni colonna è una capacità in chili e ogni cella contiene il massimo di dollari che ci sta. Con la tabella selezionata, i tasti freccia si spostano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

      Come funziona

      1. Tocca le scatole per metterle nello zaino e guardalo riempirsi in base al peso in chili.
      2. Prova a raggiungere il miglior valore possibile in dollari, oppure premi Carico migliore per vedere lo zaino migliore.
      3. Apri la vista Tabella e premi Riproduci per vedere ogni cella scegliere tra mettere e lasciare un oggetto.

      Come funziona la tabella

      Ogni riga aggiunge un oggetto e ogni colonna è una capacità da 0 fino a quella dello zaino. Una cella contiene il valore massimo che sta in quella capacità usando gli oggetti fino alla sua riga. Senza il nuovo oggetto, è la cella sopra. Con l'oggetto, se ci sta, è il suo valore più il valore migliore per il peso che resta, che si trova nella riga sopra, spostandosi a sinistra di quanto pesa l'oggetto. La cella tiene il maggiore dei due. La prima riga, senza oggetti, è tutta di zeri.

      Ricostruire gli oggetti

      La cella in basso a destra è il valore migliore. Per trovare gli oggetti, parti da lì e confrontala con la cella sopra: se è uguale, l'ultimo oggetto non serviva; se è maggiore, l'oggetto è nello zaino, quindi sottrai il suo peso e spostati in quella colonna. Sali di una riga ogni volta fino alla prima. L'app mostra questa ricostruzione in arancione ed elenca gli oggetti nello zaino sotto la tabella.

      Domande frequenti

      Che cosa significa 0/1 nel problema dello zaino 0/1?

      Ogni oggetto viene preso una volta o per niente, mai in parte e mai due volte. Se gli oggetti si potessero dividere, come chicchi di riso, prendere prima il miglior valore per unità di peso sarebbe ottimale; questo è il problema dello zaino frazionario.

      Perché non prendere prima il miglior valore per unità di peso?

      Perché gli oggetti interi possono lasciare dei vuoti. Con una capacità di 7 e oggetti di peso 1, 3, 4 e 5 che valgono 1, 4, 5 e 7, il miglior valore per unità di peso è quello dell'oggetto di peso 5, che lascia spazio solo per l'oggetto di peso 1, per un totale di 8. Gli oggetti di peso 3 e 4 insieme valgono 9.

      Quanto è veloce l'algoritmo dello zaino?

      La tabella ha (numero di oggetti + 1) per (capacità + 1) celle, ciascuna riempita in un passo. È veloce per capacità piccole, ma una capacità può essere un numero enorme, quindi in generale il problema è NP-difficile; il metodo della tabella si dice pseudo-polinomiale.

      Si può mettere lo stesso oggetto due volte?

      Qui no. Nel problema dello zaino illimitato ogni oggetto si può prendere quante volte si vuole; la tabella legge allora la cella a sinistra nella stessa riga invece della riga sopra, come nell'app del problema del resto.

      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