Versione delle 21:32, 22 lug 2019 modifica Ruthven (discussione \| contributi) Check user, Amministratori 109 279 modifiche m wklink ← Differenza precedente		Versione delle 21:20, 28 mar 2020 modifica annulla AttoBot (discussione \| contributi) Bot 495 509 modifiche m Bot: Correzione di uno o più errori comuni; modifiche estetiche Differenza successiva →
Riga 1: {{NN\|matematica\|febbraio 2013}} [[~~Immagine~~File:Knapsack.svg\|~~thumb~~miniatura\|In questo caso, la soluzione è di mettere nello zaino tre scatole gialle e tre grigie]] Il '''problema dello zaino''', detto anche '''''Knapsack problem''''', è un problema di [[Ottimizzazione (matematica)\|ottimizzazione]] [[calcolo combinatorio\|combinatoria]] posto nel modo seguente. Riga 42: Il problema dello zaino, nella versione di ottimizzazione, è di fondamentale importanza in quanto può essere risolto in maniera soddisfacente in molti casi di comune applicazione; infatti per questo problema sono disponibili buone euristiche e buoni rilassamenti. Un algoritmo di enumerazione implicita, ad esempio [[Branch and bound]], normalmente non impiega molto tempo per risolverlo. == Soluzione problema dello zaino senza limiti == Viene descritta di seguito la soluzione per il ''problema dello zaino senza limiti''. Si indichino con <math>c_1,\ldots,c_N</math> i guadagni offerti dagli oggetti, e con <math>w_1,\ldots,w_N</math> i pesi di ogni oggetto. Si desidera massimizzare il guadagno complessivo mantenendo il peso complessivo minore o uguale al peso massimo consentito <math>W</math> (vincolo). Si indichi con <math>A(k)</math> il valore massimo di guadagno che si può ottenere rispettando il vincolo che il peso complessivo sia minore odo uguale a <math>k</math>. Ovviamente <math>k\leq W</math> e <math>A(W)</math> è la soluzione del problema. Si definiscono gli <math>A(k)</math> ricorsivamente come di seguito: Riga 57: Ciò non contraddice il fatto che il problema dello zaino sia [[NP-completo]], dato che <math>W</math>, al contrario di <math>N</math>, non è polinomiale rispetto alla lunghezza dell'input del problema. Questa lunghezza è proporzionale al numero di bit in <math>W</math>, e non a <math>W</math> stesso. == Soluzione problema dello zaino 0-1 == Si indichino con <math>w_i</math> il peso dell'i-esimo oggetto e con <math>c_i</math> il suo valore. Si vuole massimizzare il valore totale rispettando il vincolo che il peso totale sia minore o uguale al peso massimo consentito <math>W</math>. Definiamo <math>A(i,j)</math> come il massimo valore che può essere trasportato con uno zaino di capacità <math>j \le W</math> avendo a disposizione solo i primi <math>i</math> oggetti. Riga 71: == Algoritmo Greedy == Martello e Toth (1990) hanno utilizzato un'[[euristica]] [[Algoritmo greedy\|greedy]] per risolvere il problema dello zaino. La loro versione ordina gli oggetti in base al loro costo unitario, vale a dire <math>\frac{c_i}{w_i}</math> e li esamina in ordine decrescente. L'oggetto corrente viene inserito se e solo se il suo peso non supera la capacità residua corrente. Questi algoritmi sono euristici, quindi non garantiscono di trovare la soluzione ottima, ma sono in grado di fornire una "buona" soluzione in tempo ragionevole; spesso questo tipo di algoritmi viene utilizzato in approcci di enumerazione implicita come gli algoritmi [[Branch and bound]]. Riga 94: \| isbn = 0-471-92420-2 \| url=http://www.or.deis.unibo.it/knapsack.html}} {{Portale\|informatica\|matematica}}▼ [[Categoria:Problemi NP-completi]] [[Categoria:Programmazione dinamica]] ▲{{Portale\|informatica\|matematica}}

Problema dello zaino: differenze tra le versioni