Problema dello zaino: differenze tra le versioni

Versione delle 17:23, 27 ago 2008

Versione delle 16:54, 22 set 2008

Riga 1:

[[Immagine:Knapsack.svg|thumb|250px|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 combinatoria posto nel modo seguente:

Riga 9 ⟶ 10:

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

:* si indica con ''W'' 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 è:

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

I vincoli:

Riga 21 ⟶ 22:

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

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

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

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

: <math>x_i \leq b_i</math> <math>\quad \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,...,N</math>

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

Il problema dello zaino è risolto spesso usando la [[programmazione dinamica]], anche se è noto che tale metodo abbia 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]]. Questi tentativi usavano tipicamente alcuni [[Gruppo (matematica)|gruppi]] oltre agli interi. [[Merkle-Hellman]] e altri algoritmi simili vennero presto abbandonati, in quanto 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]].

Riga 82:

== Bibliografia ==

* {{cite book

| authorlink = Michael R. Garey

| first = Michael R. | last = Garey

| coauthors = [[David S. Johnson]]

| year = 1979

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

| publisher = W.H. Freeman

| id = ISBN 0716710455}}

}} A6: MP9, pg.247.

* {{cite book

| authorlink = Silvano Martello

| first = Silvano | last = Martello

| coauthors = [[Paolo Toth]]

| year = 1990

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

| publisher = Wiley

| id= ISBN 0471924202}}

}}

[[Categoria:algoritmi]]