Newsgroup: it.comp.lang.c++
Titolo: problema dello zaino 01: risolvere

Salve ragazzi ho un problema, devo fare un esame lunedě e non so risolvere
il "problema dello zaino 01" in modo efficiente con la programmazione
dinamica, spero che qualcuno di voi mi possa aiutare, vi prego fate presto e
rispondetemi a casa se possibile ok?
Grazie s'aribbeccamo

 wrote in message
Et%o4.117732$C3.12...@news.infostrada.it...

Se ci spieghi cosa č questo "problema dello zaino" certamente... detto cosě
sembra piů qualcosa per organizzare i pic-nic che per altro.
--
| /
| \Byte - Andrea Briganti
E-Mail 
kbyt...@freemail.it
ICQ 40872731

 sembra piů qualcosa per organizzare i pic-nic che per altro.
E' un classico compito da svolgere per un esame - quindi, se questo e'
il caso, meriterebbe di non essere svolto in dettaglio.
Hai uno zaino di capacita' data; e, di fronte a te, un insieme di
items ognuno dei quali ha associata una dimensione ed un valore.  Devi
scrivere una procedura per determinare quali items prendere in modo da
avere nello zaino il massimo valore possibile.
Tipicamente la soluzione si trova con un algoritmo ricursivo; una
buona analisi e' fatta ad es. sul Sedgewick (Algorithms in *, 3rd
ed.); alla quale rimando chi ha fatto la domanda (visto che, se
presenta come soluzione quella del Sedgewick, nota a tutti gli
esaminatori, verra' #@$%&ato immediatamente :-)
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

 esaminatori, verra' #@$%&ato immediatamente :-)
Si, anche se il modo ricorsivo puň essere molto dispendioso se gli elementi
e gli zaini sono molti...
Nel caso di piů zaiini č forse meglio una tecnica golosa, o sbaglio?


e gli zaini sono molti...
Premesso che io lo conoscevo semplicemente come problema dello zaino
e non ho risposto proprio perche` immaginavo si trattasse di un compito
da esame... qualunque tecnica e` dispendiosa perche` il problema e`
NP-completo.
Paolo
--------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
--------------------------------------------------

NP-completo.
Il problema dello zaino č differente da quello dello zaino 0-1, ma qui ci
riferiamo a nomenclatura tutt'altro che standard, quindi magari parliamo
della stessa cosa.
Non credo che "qualunque tecnica sia dispendiosa", o perlomeno sono sicuro
che ci sono algoritmi migliori e peggiori che risolvano il problema
(sicuramente c'č di meglio che provare tutte le combinazioni possibili...).
Resta il fatto che non so cosa si intenda per "NP-completo", puoi
spiegarmelo?
Anch'io devo risolvere il problema e sto cercando qualcuno che mi dia una
risposta un po' piů precisa (del tipo "prova cosě: ..."). La tecnica da
applicare č la programmazione dinamica.
_
Francesco "SiSkO" Napolitano

spiegarmelo?
Difficile da spiegare in 4 parole c'e` di mezzo la teoria della 
calcolabilita`. Diciamo che e` una classe di problemi per i quali
non e` noto un algoritmo deterministico che trovi la soluzione
in tempi ragionevoli. In effetti per il problema dello zaino (e molti
altri) l'unico algoritmo noto e` sostanzialmente quello di provare tutte
le soluzioni possibili... Chiaramente se il numero degli oggetti e`
maggiore di un certo N (piccolo) per quanto ottimizzato nessun algoritmo
potra` dare una risposta in tempi ragionevoli.
Di solito per questi problemi si ricorre ad algoritmi euristici che
cercano una soluzione approssimata (con tempi decisamente
piu` accettabili).


 applicare č la programmazione dinamica.
Martello and Toth, _Knapsack Problems: Algorithms and Computer
Implementations_, Wiley 1990, e` il testo "definitivo" sull'argomento.
Devo ammettere di essere influenzato anche dal fatto che questi due
luminari della ricerca operativa insegnano qui a Bologna e sono stati
miei professori:-).
Fra i riferimenti che trovi in linea, forse il piu` lucidamente e
semplicemente presentato e` quello di Moshe Sniedovich,
http://www.maths.mu.oz.au/~moshe/recor/knapsack/knapsack.html
(mi pare che il vostro problema sia appunto lo _unbounded_ knapsack,
giusto?). Con un View/HTML Source di questa pagina, vedrai la
soluzione in Javascript (non leggibilissima, ma, insomma...!-).
Non trascurerei anche 
http://mat.gsia.cmu.edu/orclass/integer/integer.html
(un piu` generale ma semplice tutorial di integer programming, che
mostra particolarmente bene l'uso del branch-and-bound, dei cutting
planes di Gomory e non, ecc; il knapsack e` visto un po' di sfuggita,
si concentra su problemi piu` spinosi); al contrario, una presentazione
estremamente pragmatica e mirata la trovi nella pagina
http://www.stanford.edu/~jonmac/lchs/final3.htm
 (cerca "knapsack"
entro la pagina, che e` grandina...).
Alex

 Non per il problema dello Zaino...
Non esageriamo...!  Il fatto che non si possa risolvere in tempo
polinomiale non significa che tutti gli approcci siano egualmente
buoni (o egualmente cattivi).  Se un algoritmo A1 ha un tempo
medio di esecuzione che e` la meta` di un altro algoritmo A2,
il buonsenso ci dice che A1 e` migliore -- anche se e` ovvio che
o entrambi sono polinomiali, o non lo e` nessuno dei due:-).
Alex

buoni (o egualmente cattivi).
Mi riferivo alla trattabilita` di questi problemi, chiaramente se
devi risolverne uno impiegare 1 mese e meglio che impiegarne 2...
ma dal punto di vista della trattabilita` ridurre i tempi di una
costante moltiplicativa in generale non ha molto senso.


 asintoticamente le due grandezze si equivalgono...
Non riesco a rispolverare i vecchi appunti ma ti assicuro che la differenza
non è solo nelle costanti rispetto alla tecnica golosa.
L'unico inconveniente è che si devono fare dei compromessi accettando anche
possibili soluzioni non ottimali.


possibili soluzioni non ottimali.
Non stavo discutendo di algoritmi approssimati, la cui complessita` nel
caso pessimo e` comunque sempre superpolinomiale (altrimenti il
problema non sarebbe NP e qualcuno avrebbe preso il Nobel).
