Problema dello zaino: differenze tra le versioni

Versione delle 09:28, 20 ago 2025

Versione attuale delle 08:50, 12 set 2025

Riga 41:

== Complessità computazionale ==

Il problema dello zaino è risolto spesso usando la [[programmazione dinamica]], anche se è noto che questo metodo ha un tempo di risoluzione non lineare per questo genere di problema. Il problema generale dello zaino è un problema [[NP-difficile]] 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 poiché 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 62:

|}

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 ==

Riga 236:

=== 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 ==

Riga 414:

* {{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}}