Problema dello zaino: differenze tra le versioni

Versione delle 17:23, 27 ago 2008

Versione attuale delle 08:50, 12 set 2025

(66 versioni intermedie di 51 utenti non mostrate)

Riga 1:

{{NN|matematica|febbraio 2013}}

Il '''Problema dello zaino''', detto anche '''Knapsack problem''', è un problema di ottimizzazione combinatoria posto nel modo seguente:

[[File:Knapsack Problem Illustration.svg|miniatura|In questo caso, la soluzione è di mettere nello zaino tre libri gialli e tre grigi]]

Il '''problema dello zaino''', o {{Inglese|'''Knapsack problem'''}}, è un problema di [[Ottimizzazione (matematica)|ottimizzazione]] [[calcolo combinatorio|combinatoria]] posto nel modo seguente<ref>{{cita libro|cognome=Cormen|nome=Thomas H.|cognome2=Leiserson|nome2=Charles E.|cognome3=Rivest|nome3=Ronald L.|cognome4=Stein|nome4=Clifford|titolo=Introduction to Algorithms|edizione=4|editore=MIT Press|anno=2022|isbn=978-0-262-04630-5|p=394-399}}</ref>.

:sia dato uno [[zaino]] che possa supportare un determinato peso. Siano dati inoltre ''N'' oggetti, ognuno dei quali caratterizzato da un ''peso'' e un'''utilità'' (ovvero un ''guadagno''). Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere la maggiore utilità senza eccedere nel peso sostenibile dallo zaino stesso.

:Sia dato uno [[zaino]] che possa sopportare un determinato peso e siano dati <math>N</math> oggetti, ognuno dei quali caratterizzato da un ''peso'' e un ''valore''. Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il maggiore valore senza eccedere il peso sostenibile dallo zaino stesso.

Il problema rappresenta un classico esempio di [[programmazione dinamica]] e illustra perfettamente il concetto di [[sottostruttura ottimale]], dove la soluzione ottimale del problema può essere costruita combinando soluzioni ottime dei sottoproblemi<ref>{{cita libro|cognome=Kleinberg|nome=Jon|cognome2=Tardos|nome2=Éva|titolo=Algorithm Design|editore=Pearson|anno=2013|isbn=978-0321295354|p=260-267}}</ref>.

== Introduzione ==

Riga 7 ⟶ 12:

Il problema espresso in maniera più formale diventa:

:* ognuno degli ''<math>N''</math> oggetti possiede un peso <math>w_i</math> e un'utilità valore <math>c_i</math>;

:* si indica con ''<math>W''</math> il peso massimo sopportabile dallo zaino;

:* la possibilità che un oggetto venga inserito o meno nello zaino è espressa dalle variabili intere <math>x_i</math>={0,1} con i=''1...N''

La [[funzione obiettivo]] da massimizzare è:

: <math>max Z = \sum_{i=1}^N c_i\cdot x_i.</math>

I vincoli:

: <math>\sum_{i=1}^N w_i\cdot x_i\leq W.</math>

In base al tipo di variabili <math>x_i</math> si ha poi la distinzione in:

:* '''problema dello zaino 0-1''':

:: <math>x_i=\left\{0,1\right\}</math> \quad <math>\forall i=1,...\ldots,N,</math>

: ogni oggetto può esserci o non esserci senza ripetizioni (abbiamo un solo esemplare di ciascun oggetto);

* '''problema dello zaino con limiti'''

: ogni oggetto può esserci o non esserci senza ripetizioni;

:: <math>x_i \leq b_i \quad \forall i=1,\ldots,N,</math>

:* '''problema dello zaino con limiti'''

: ogni oggetto può apparire nello zaino al massimo <math>b_i</math> volte (abbiamo <math>b_1</math> esemplari dell'oggetto 1, <math>b_2</math> esemplari dell'oggetto 2 e così via);

* '''problema dello zaino senza limiti'''

: <math>x_i \leq b_i</math> <math>\forall i=1,...,N</math>.

: ogni oggetto non può apparire nello zaino più di un certo numero di volte;

:* '''problema dello zaino senza limiti'''

:: <math>x_i \in \N \quad \forall i=1,\ldots,N,</math>

: ogni oggetto può apparire nello zaino un numero arbitrario di volte.

== Complessità computazionale ==

Il problema dello zaino è risolto spesso usando la [[programmazione dinamica]], anche se è noto che talequesto metodo abbiaha un tempo di risoluzione non lineare per questo genere di problema. Il problema generale dello zaino è un problema [[NP-harddifficile]], e questo ha indirizzato la ricerca verso il problema [[Subset-sum]] come base per il sistema di [[Public key infrastructure|crittografia a chiave pubblica]], come [[Merkle-Hellman]]<ref>{{cita libro|cognome=Garey|nome=Michael R.|cognome2=Johnson|nome2=David S.|titolo=Computers and Intractability: A Guide to the Theory of NP-Completeness|url=https://archive.org/details/computersintract0000gare|editore=W.H. Freeman|anno=1979|isbn=0-7167-1045-5|p=[https://archive.org/details/computersintract0000gare/page/246 247]-248}}</ref>. Questi tentativi usavano tipicamente alcuni [[Gruppo (matematica)|gruppi]] oltre agli interi. [[Merkle-Hellman]] e altri algoritmi simili vennero presto abbandonati, in quantopoiché i sottoproblemi di somma che producevano erano risolvibili da algoritmi lineari.

La versione decisionale di questo problema è [[NP-completo|NP-completa]] e infatti è uno dei [[21 problemi NP-completi di Karp]].

Il problema dello zaino, nella versione di ottimizzazione, è di fondamentale importanza in quanto, perpuò molteessere istanzerisolto diin comunemaniera applicazione,soddisfacente puòin esseremolti risoltocasi indi manieracomune soddisfacenteapplicazione; infatti per questo problema, infatti, sono disponibili buone euristiche e buoni rilassamenti. Un algoritmo di enumerazione implicita, (ad esempio [[Branch and bound]]), normalmente non impiega molto tempo per risolverlo.

=== Analisi della complessità ===

== Soluzione problema dello zaino senza limiti==

{| class="wikitable"

|-

! Variante !! Complessità temporale !! Complessità spaziale !! Note

|-

| Zaino 0-1 (DP) || O(nW) || O(nW) o O(W) || Pseudo-polinomiale

|-

| Zaino senza limiti (DP) || O(nW) || O(W) || Pseudo-polinomiale

|-

| Zaino frazionario (Greedy) || O(n log n) || O(1) || Polinomiale

|-

| Branch and Bound || O(2ⁿ) || O(n) || Esponenziale (caso peggiore)

|}

La complessità O(nW) è '''pseudo-polinomiale''' perché dipende dal valore numerico W, non dalla sua lunghezza in bit (log W)<ref>{{cita libro|cognome=Dasgupta|nome=Sanjoy|cognome2=Papadimitriou|nome2=Christos|cognome3=Vazirani|nome3=Umesh|titolo=Algorithms|url=https://archive.org/details/algorithms0000dasg|editore=McGraw-Hill|anno=2008|isbn=978-0073523408|p=[https://archive.org/details/algorithms0000dasg/page/174 175]-178}}</ref>.

== 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,\dotsldots,c_nc_N</math> i guadagni offerti dagli oggetti, e con <math>w_1,\dotsldots,w_nw_N</math> i pesi di ogni oggetto. Si desidera massimizzare il guadagno complessivo rispettando il vincolo chemantenendo il peso complessivo siaminore inferioreo uguale al peso massimo consentito <math>W</math> (vincolo). Ora, siSi indichi con <math>A(ik)</math> il valore massimo di guadagno che si può ottenere rispettando il vincolo che il peso complessivo sia minore odo uguale ada <math>ik</math>. Ovviamente <math>ik\leq W</math>, e <math>A(W)</math> saràè la soluzione del nostro problema.

Si definiscono gli <math>A(ik)</math> ricorsivamente come di seguito:

* <math>A(0) = 0;</math>,

* <math>A(ik)=\max \lbrace c_j + A(ik - w_j) | w_j \le ik \rbrace. </math>.

Quiavendo si consideraconsiderato zero il massimo dell'insieme vuoto. Se si tabulano i risultati a partire da <math>A(0)</math> fino a <math>A(CW)</math> si ottiene la soluzione. Dato che il calcolo di ogni <math>A(ik)</math> implica l'esame di <math>nN</math> oggetti (che sono, tutti stati calcolati in precedenza), e visto che ci sono <math>CW</math> valori di <math>A(ik)</math> da calcolare, il tempo impiegato per trovare la soluzione è <math>O(nCNW)</math>.

Ciò non contraddice il fatto che il problema dello zaino èsia [[NP-completo]], dato che <math>CW</math>, al contrario di <math>nN</math>, non è polinomiale rispetto alla lunghezza dell'input del problema. TaleQuesta lunghezza è proporzionale al numero di bit in <math>CW</math>, e non a <math>CW</math> stesso.

=== Implementazione zaino senza limiti ===

== Soluzione problema dello zaino 0-1==

<syntaxhighlight lang="text">

Come sopra, si indicano i costi con <math>c_1,\dots,c_n</math> e i corrispondenti valori con <math>v_1,\dots,v_n</math>. Si vuole massimizzare il valore totale soggetto al vincolo che il costo totale deve essere minor di <math>C</math>. Si definisce una funzione ricorsiva <math>A(i,j)</math> che sia il massimo valore che può essere ottenuto con un costo minore o uguale a <math>j</math> utilizzando fino a <math>i</math> oggetti.

KNAPSACK_UNLIMITED(pesi, valori, n, W):

// Inizializzazione

dp[0] = 0

for w = 1 to W:

dp[w] = 0

// Riempimento tabella DP

for w = 1 to W:

for i = 1 to n:

if pesi[i] <= w:

dp[w] = max(dp[w], dp[w - pesi[i]] + valori[i])

return dp[W]

</syntaxhighlight>

== Soluzione problema dello zaino 0-1 ==

Si può definire <math>A(i,j)</math> in modo ricorsivo come di seguito:

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.

* <math>A(0, j) = 0</math>,

* <math>A(i, 0) = 0</math>,

* <math>A(i,j) = A(i - 1, j)</math> se <math>c_i > j</math>,

* <math>A(i,j) = \max \lbrace A(i - 1, j), A(i - 1, j - c_i) + v_i \rbrace </math> se <math>c_i\le j</math>.

Si può definire <math>A(i,j)</math> ricorsivamente come segue:

La soluzione può essere allora trovata calcolando <math>A(n,C)</math>. Per farlo in modo efficiente si può usare una tabella che memorizzi i calcoli fatti precedentemente. Questa soluzione impiegherà quindi un tempo proporzionale a <math>O(nC)</math> e uno spazio anch'esso proporzionale a <math>O(nC)</math>, anche se con alcune piccole modifiche si può ridurre lo spazio utilizzato a <math>O(C)</math>.

* <math>A(0, j) = 0,</math>

* <math>A(i, 0) = 0,</math>

* <math>A(i,j) = A(i - 1, j)</math> se <math>w_i > j,</math>

* <math>A(i,j) = \max \lbrace A(i - 1, j), A(i - 1, j - w_i) + c_i \rbrace </math> se <math>w_i\le j.</math>

Si può trovare la soluzione calcolando <math>A(n,W)</math>. Per farlo in modo efficiente si può usare una tabella che memorizzi i calcoli fatti precedentemente. Questa soluzione impiegherà quindi un tempo proporzionale a <math>O(nW)</math> e uno spazio anch'esso proporzionale a <math>O(nW)</math>, anche se con alcune piccole modifiche si può ridurre lo spazio utilizzato a <math>O(W)</math>.

=== Implementazione dettagliata zaino 0-1 ===

==== Versione con tabella completa ====

<syntaxhighlight lang="text">

KNAPSACK_01_FULL(pesi, valori, n, W):

// Creazione tabella DP

dp = array[n+1][W+1]

// Inizializzazione casi base

for i = 0 to n:

dp[i][0] = 0

for w = 0 to W:

dp[0][w] = 0

// Riempimento tabella

for i = 1 to n:

for w = 1 to W:

// Non includiamo l'oggetto i

dp[i][w] = dp[i-1][w]

// Includiamo l'oggetto i se possibile

if pesi[i] <= w:

dp[i][w] = max(dp[i][w], dp[i-1][w-pesi[i]] + valori[i])

return dp[n][W]

</syntaxhighlight>

==== Versione ottimizzata per spazio ====

<syntaxhighlight lang="text">

KNAPSACK_01_OPTIMIZED(pesi, valori, n, W):

// Array monodimensionale

dp = array[W+1]

// Inizializzazione

for w = 0 to W:

dp[w] = 0

// Processa ogni oggetto

for i = 1 to n:

// Scorri da destra a sinistra per evitare conflitti

for w = W down to pesi[i]:

dp[w] = max(dp[w], dp[w - pesi[i]] + valori[i])

return dp[W]

</syntaxhighlight>

=== Ricostruzione della soluzione ===

Per ricostruire quali oggetti fanno parte della soluzione ottimale:

<syntaxhighlight lang="text">

RECONSTRUCT_SOLUTION(dp, pesi, valori, n, W):

soluzione = []

i = n

w = W

while i > 0 and w > 0:

// Se il valore deriva dall'inclusione dell'oggetto i

if dp[i][w] != dp[i-1][w]:

soluzione.append(i)

w = w - pesi[i]

i = i - 1

return reverse(soluzione)

</syntaxhighlight>

=== Esempio passo-passo ===

Consideriamo 3 oggetti con zaino di capacità 5:

* Oggetto 1: peso=2, valore=1

* Oggetto 2: peso=3, valore=4

* Oggetto 3: peso=4, valore=7

'''Tabella DP:'''

{| class="wikitable"

|-

! i\w !! 0 !! 1 !! 2 !! 3 !! 4 !! 5

|-

| 0 || 0 || 0 || 0 || 0 || 0 || 0

|-

| 1 || 0 || 0 || 1 || 1 || 1 || 1

|-

| 2 || 0 || 0 || 1 || 4 || 4 || 5

|-

| 3 || 0 || 0 || 1 || 4 || 7 || 7

|}

'''Soluzione ottimale:''' Valore = 7 (solo oggetto 3)

== Algoritmo Greedy ==

Martello e Toth (1990) proposero un'[[euristica]] [[Algoritmo greedy|greedy]] per risolvere il problema dello zaino. La loro versione ordina gli oggetti in ordine decrescente di peso per inserirli nello zaino fino all'esaurimento dello spazio disponibile. Se ''k'' è il massimo numero di oggetti che possono essere inseriti nello zaino, l'algoritmo [[Algoritmo greedy|greedy]] garantisce che ne siano inseriti nello zaino almeno <math>\frac{k}{2}</math>.

Martello e Toth (1990) hanno utilizzato un'[[euristica]] [[Algoritmo greedy|greedy]] per risolvere il problema dello zaino<ref>{{Cita libro|nome=Silvano|cognome=Martello|coautori=Paolo Toth|anno=1990|titolo=Knapsack Problems: Algorithms and Computer Implementations|editore=Wiley|isbn=0-471-92420-2|url=http://www.or.deis.unibo.it/knapsack.html}}</ref>. 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.

Sono possibili molte variazioni di questo algoritmo, la più efficiente prevede di ordinare gli elementi in base al loro costo unitario, vale a dire <math>\frac{c_i}{w_i}</math> ed inserirli in ordine decrescente (euristica CUD).

=== Implementazione algoritmo greedy ===

È bene far notare come questi algoritmi siano euristici: essi, quindi, non garantiscono l'ottimalità della soluzione 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]].

<syntaxhighlight lang="text">

KNAPSACK_GREEDY(pesi, valori, n, W):

// Calcola rapporto valore/peso

rapporti = []

for i = 1 to n:

rapporti[i] = valori[i] / pesi[i]

// Ordina per rapporto decrescente

oggetti_ordinati = sort_by_ratio_desc(rapporti)

// Algoritmo greedy

peso_corrente = 0

valore_totale = 0

soluzione = []

for oggetto in oggetti_ordinati:

if peso_corrente + pesi[oggetto] <= W:

soluzione.append(oggetto)

peso_corrente += pesi[oggetto]

valore_totale += valori[oggetto]

return valore_totale, soluzione

</syntaxhighlight>

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]].

=== Analisi del rapporto di approssimazione ===

Per il problema dello zaino 0-1, l'algoritmo greedy non garantisce alcun rapporto di approssimazione costante. Tuttavia, per il '''problema dello zaino frazionario''' (dove si possono prendere frazioni di oggetti), l'algoritmo greedy è ottimale<ref>{{cita libro|cognome=Vazirani|nome=Vijay V.|titolo=Approximation Algorithms|url=https://archive.org/details/approximationalg0000vazi|editore=Springer|anno=2001|isbn=978-3540653677|p=[https://archive.org/details/approximationalg0000vazi/page/74 74]-77}}</ref>.

== Rilassamento continuo ==

Si dimostra che il rilassamento continuo del problema dello zaino è equivalente all'euristica CUD quando si permettono valori in [0, 1] delle variabili <math>x_i</math> (in particolare una sola variabile avrà valore non binario). In questo modo euristica e rilassamento possono essere risolti simultaneamente in maniera efficiente.

Si dimostra che il rilassamento continuo del problema dello zaino è equivalente all'euristica CUD quando si permettono valori in <math>[0, 1]</math> delle variabili <math>x_i</math>, in particolare una sola variabile avrà valore non binario. In questo modo euristica e rilassamento possono essere risolti simultaneamente in maniera efficiente.

=== Soluzione del rilassamento ===

<syntaxhighlight lang="text">

KNAPSACK_FRACTIONAL(pesi, valori, n, W):

// Ordina per rapporto valore/peso decrescente

oggetti = sort_by_value_weight_ratio_desc(pesi, valori)

peso_corrente = 0

valore_totale = 0

soluzione = array[n] // frazione di ogni oggetto

for i = 1 to n:

if peso_corrente + pesi[oggetti[i]] <= W:

// Prendi tutto l'oggetto

soluzione[oggetti[i]] = 1

peso_corrente += pesi[oggetti[i]]

valore_totale += valori[oggetti[i]]

else:

// Prendi frazione dell'oggetto

frazione = (W - peso_corrente) / pesi[oggetti[i]]

soluzione[oggetti[i]] = frazione

valore_totale += frazione * valori[oggetti[i]]

break

return valore_totale, soluzione

</syntaxhighlight>

== Algoritmi di approssimazione ==

=== Algoritmo 2-approssimato ===

Un semplice algoritmo 2-approssimato per il problema dello zaino 0-1:

<syntaxhighlight lang="text">

KNAPSACK_2_APPROX(pesi, valori, n, W):

// Soluzione 1: algoritmo greedy

valore_greedy, sol_greedy = KNAPSACK_GREEDY(pesi, valori, n, W)

// Soluzione 2: oggetto di valore massimo

valore_max = 0

oggetto_max = 0

for i = 1 to n:

if pesi[i] <= W and valori[i] > valore_max:

valore_max = valori[i]

oggetto_max = i

// Restituisci la migliore delle due

if valore_greedy >= valore_max:

return valore_greedy, sol_greedy

else:

return valore_max, [oggetto_max]

</syntaxhighlight>

=== FPTAS (Fully Polynomial-Time Approximation Scheme) ===

Esiste un FPTAS per il problema dello zaino che garantisce una soluzione (1+ε)-approssimata in tempo O(n³/ε)<ref>{{cita libro|cognome=Williamson|nome=David P.|cognome2=Shmoys|nome2=David B.|titolo=The Design of Approximation Algorithms|editore=Cambridge University Press|anno=2011|isbn=978-0521195270|p=65-69}}</ref>:

<syntaxhighlight lang="text">

KNAPSACK_FPTAS(pesi, valori, n, W, epsilon):

// Scala i valori per ridurre la complessità

V_max = max(valori)

K = epsilon * V_max / n

valori_scalati = []

for i = 1 to n:

valori_scalati[i] = floor(valori[i] / K)

// Risolvi con DP sui valori scalati

return KNAPSACK_BY_VALUE(pesi, valori_scalati, n, W, K)

</syntaxhighlight>

== Varianti avanzate ==

=== Problema dello zaino multidimensionale ===

Estensione con più vincoli di peso:

<syntaxhighlight lang="text">

// Zaino con m dimensioni (es: peso, volume, costo)

MULTIDIMENSIONAL_KNAPSACK(pesi, valori, n, capacita, m):

// DP con m+1 dimensioni

dp = array[n+1][capacita[1]+1]...[capacita[m]+1]

// Inizializzazione

// ... (tutti gli elementi a 0)

for i = 1 to n:

for c1 = capacita[1] down to pesi[i][1]:

for c2 = capacita[2] down to pesi[i][2]:

// ... per tutte le m dimensioni

for cm = capacita[m] down to pesi[i][m]:

dp[c1][c2]...[cm] = max(

dp[c1][c2]...[cm],

dp[c1-pesi[i][1]][c2-pesi[i][2]]...[cm-pesi[i][m]] + valori[i]

)

return dp[capacita[1]][capacita[2]]...[capacita[m]]

</syntaxhighlight>

=== Problema dello zaino con conflitti ===

Alcuni oggetti non possono essere selezionati insieme:

<syntaxhighlight lang="text">

KNAPSACK_WITH_CONFLICTS(pesi, valori, n, W, conflitti):

// Usa branch and bound o programmazione intera

// conflitti[i][j] = true se oggetti i e j sono in conflitto

function is_valid(soluzione):

for i in soluzione:

for j in soluzione:

if i != j and conflitti[i][j]:

return false

return true

// Algoritmo di backtracking

return BACKTRACK_KNAPSACK(pesi, valori, W, conflitti, [], 0)

</syntaxhighlight>

== Applicazioni pratiche ==

=== Allocazione risorse ===

* '''Budget allocation:''' Distribuzione ottimale di fondi tra progetti

* '''Portfolio optimization:''' Selezione di investimenti con budget limitato

* '''Resource scheduling:''' Assegnazione di risorse computazionali

=== Informatica ===

* '''Memory management:''' Ottimizzazione dell'uso della memoria cache

* '''Bandwidth allocation:''' Distribuzione della banda di rete

* '''Load balancing:''' Distribuzione del carico sui server

=== Logistica ===

* '''Cargo loading:''' Caricamento ottimale di container e aerei

* '''Cutting stock:''' Minimizzazione dello spreco in taglio di materiali

* '''Bin packing:''' Ottimizzazione dello spazio in magazzini

=== Crittografia ===

* '''Subset-sum cryptography:''' Base per sistemi crittografici (ormai obsoleti)

* '''Lattice-based cryptography:''' Varianti moderne per crittografia post-quantistica

== Strumenti e librerie ==

=== Implementazioni efficienti ===

Per problemi reali di grandi dimensioni, sono disponibili solver specializzati:

* '''CPLEX:''' Solver commerciale per programmazione lineare intera

* '''Gurobi:''' Solver avanzato con supporto per problemi di zaino

* '''SCIP:''' Solver open-source per programmazione intera

* '''OR-Tools:''' Libreria Google per ottimizzazione combinatoria

== Note ==

<references/>

== Bibliografia ==

* {{citeCita booklibro

| authorlinknome = Michael R. | cognome = Garey

| firstcoautori = MichaelDavid RS. | last = GareyJohnson

| anno = 1979

| coauthors = [[David S. Johnson]]

| titolo = Computers and Intractability: A Guide to the Theory of NP-Completeness

| year = 1979

| url = https://archive.org/details/computersintract0000gare | editore = W.H. Freeman

| title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]

| isbn = 0-7167-1045-5}}

| publisher = W.H. Freeman

* {{Cita libro

| id = ISBN 0716710455

| nome = Silvano | cognome = Martello

}} A6: MP9, pg.247.

| coautori = Paolo Toth

| anno = 1990

| titolo = Knapsack Problems: Algorithms and Computer Implementations

| editore = Wiley

| isbn = 0-471-92420-2

| url=http://www.or.deis.unibo.it/knapsack.html}}

* {{cita libro|cognome=Cormen|nome=Thomas H.|cognome2=Leiserson|nome2=Charles E.|cognome3=Rivest|nome3=Ronald L.|cognome4=Stein|nome4=Clifford|titolo=Introduction to Algorithms|edizione=4|editore=MIT Press|anno=2022|isbn=978-0-262-04630-5}}

* {{cita libro|cognome=Kleinberg|nome=Jon|cognome2=Tardos|nome2=Éva|titolo=Algorithm Design|editore=Pearson|anno=2013|isbn=978-0321295354}}

* {{cita libro|cognome=Vazirani|nome=Vijay V.|titolo=Approximation Algorithms|url=https://archive.org/details/approximationalg0000vazi|editore=Springer|anno=2001|isbn=978-3540653677}}

* {{cita libro|cognome=Williamson|nome=David P.|cognome2=Shmoys|nome2=David B.|titolo=The Design of Approximation Algorithms|editore=Cambridge University Press|anno=2011|isbn=978-0521195270}}

== Voci correlate ==

* {{cite book

* [[Programmazione dinamica]]

| authorlink = Silvano Martello

* [[Sottostruttura ottimale]]

| first = Silvano | last = Martello

* [[Algoritmo greedy]]

| coauthors = [[Paolo Toth]]

* [[Problema di ottimizzazione]]

| year = 1990

* [[NP-completezza]]

| title = [[Knapsack Problems: Algorithms and Computer Implementations]]

* [[Algoritmo di approssimazione]]

| publisher = Wiley

* [[Branch and bound]]

}}

* [[Subset-sum]]

== Collegamenti esterni ==

[[Categoria:algoritmi]]

* {{Collegamenti esterni}}

[[Categoria:ricerca operativa]]

* {{FOLDOC|knapsack problem|knapsack problem}}

* {{en}} [https://web.stanford.edu/class/cs161/schedule.html Stanford CS161: Knapsack Problem]

* {{en}} [https://cp-algorithms.com/dynamic_programming/knapsack.html CP-Algorithms: Knapsack Problem]

{{Portale|informatica|matematica}}

{{Link AdQ|fr}}

[[Categoria:Problemi NP-completi]]

[[cs:Problém batohu]]

[[Categoria:Programmazione dinamica]]

[[de:Rucksackproblem]]

[[Categoria:Algoritmi di ottimizzazione]]

[[en:Knapsack problem]]

[[es:Problema de la mochila]]

[[fa:مسئله کوله‌پشتی]]

[[fr:Problème du sac à dos]]

[[ja:ナップサック問題]]

[[ko:배낭 문제]]

[[nl:Knapzakprobleem]]

[[pl:Problem plecakowy]]

[[pt:Problema da mochila]]

[[ru:Задача о ранце]]

[[sv:Kappsäcksproblemet]]

[[tr:Knapsack problemi]]

[[vi:Bài toán xếp ba lô]]

[[zh:背包问题]]