Sommario:
Definizione - Che cosa significa Problema allo zaino?
Il problema dello zaino è un problema di ottimizzazione utilizzato per illustrare sia il problema che la soluzione. Deriva il suo nome da uno scenario in cui si è vincolati al numero di oggetti che possono essere inseriti in uno zaino di dimensioni fisse. Dato un insieme di articoli con pesi e valori specifici, l'obiettivo è quello di ottenere il maggior valore possibile nello zaino, dato il vincolo di peso dello zaino.
Techopedia spiega il problema dello zaino
Il problema dello zaino è un esempio di un problema di ottimizzazione combinatoria, un argomento in matematica e informatica sulla ricerca dell'oggetto ottimale tra un insieme di oggetti. Questo è un problema che è stato studiato per più di un secolo ed è un problema di esempio comunemente usato nell'ottimizzazione combinatoria, in cui è necessario un oggetto ottimale o una soluzione finita in cui non è possibile una ricerca esaustiva. Il problema si può trovare in scenari del mondo reale come l'allocazione delle risorse in vincoli finanziari o persino nella selezione di investimenti e portafogli. Può anche essere trovato in campi come la matematica applicata, la teoria della complessità, la crittografia, la combinatoria e l'informatica. È facilmente il problema più importante nella logistica.
Nel problema dello zaino, gli articoli dati hanno almeno due attributi: il valore di un articolo, che ne influenza la sua importanza, e il peso o il volume di un articolo, che è il suo aspetto di limitazione. Poiché una ricerca esaustiva non è possibile, è possibile suddividere i problemi in sotto-problemi minori ed eseguirlo in modo ricorsivo. Questa è chiamata una sottostruttura ottimale. Si tratta di un solo oggetto alla volta e il peso attuale è ancora disponibile nello zaino. Il risolutore di problemi deve solo decidere se prendere l'oggetto o meno in base al peso che può ancora essere accettato. Tuttavia, se si tratta di un programma, il ricalcolo non è indipendente e causerebbe problemi. Qui è possibile applicare tecniche di programmazione dinamica. Le soluzioni a ciascun sotto-problema vengono archiviate in modo tale che il calcolo debba avvenire una sola volta.
