Newsgroup: it.comp.lang.c
Titolo: Problema dello zaino.

Leggendo la spiegazione dello zaino sul libro "Algoritmi in C" mi č sorto un
dubbio:
il problema consiste nel determinare la combinazione di oggetti che un
ipotetico ladro, savligiata una cassaforte contente N tipi di oggetti(di
ogni tipo do oggetto esistono infiniti esemplari) e  avendo a disposizione
solo uno zaino di dimensione M, dovrebbe scegliere al fine di massimizzare
il valore totale degli oggetti prelevati.
Sul libro l'esercizio č risolto richiamandosi alla programmazione dinamica.
A me č venuto in mente il seguente algoritmo:
- calcolare il "rendimento" di ogni oggetto: valore/peso.
-riempire lo zaino iniziando con gli oggetti a rendimento maggiore fino a
quando lo zaino non contiene piů oggetti.

 quando lo zaino non contiene piů oggetti.
il problema dello zaino non viene insegnato a caso,
in quanto la soluzione che ti propongono
e' la migliore possibile.
infatti la tua soluzione non funziona.
immagina di avere tre oggetti (con il tuo sistema):
valore     volume
4            1
4            1
9            3
e di avere lo zaino di volume 3.
tu riempiresti lo zaino con i primi due oggetti
(hanno rendimento 4/1=4)
ottenendo un valore di otto.
invece se tu avessi preso solo il terzo
oggetto (scartato perche' ha rendimento=3)
avresti portato a casa un valore pari a 9,
che e' maggiore di 8.

quando lo zaino non contiene piů oggetti.
Devi distinguere tra due diverse versioni del problema dello zaino.
C'č il problema dello zaino continuo oppure il problema dello zaino
discreto.
Il problema discreto č esattamente quello da te citato: gli oggetti
sono interi e non possono essere divisi in parti o fatti a pezzi.
Il problema continuo č invece la versione in cui le parti possono
essere scomposte (per esempio, polvere d'oro, polvere d'argento,
polvere di platino).
Il problema continuo puň essere risolto con tecniche greedy (come
quella da te evidenziata), al contrario di quello discreto.

Il problema dello zaino (knapsak credo) ha diversi approci:
io conosco 2 tecniche esatte e due algoritmi detti greedy.
1) il primo, piu' ingenuo, consiste nel provare tutte le 2**N
combinazioni per cercare "la migliore combinazione". Si tratta
quindi di cercare solo il MAX, qualunque deifinizione se ne dia
(MAX valore in $$, MAX peso, MAX rapporto Valore/Peso ecc..)
L' algoritmo si conclude in un numero ben noto di passi,
2 pow N dove N numero degli oggetti singoli. Chiaro che un tale
costo lo fa bocciare subito per valori di N sopra la la decina.
La soluzione trovata e' CERTAMENTE la MIGLIORE!!
2) Altra tecnica che porta alla combinazione SICURAMENTE MIGLIORE
e' (non so' citare in nome) quella de seguire un albero di ricerca
che si "sfrondi" continuamente all' incontrare soluzioni impropo-
nibili.
es: Indiana Jones trova il tesoro di Montezuma: 5000 pezzi preziosi.
nel tentativo di riempire lo zaino anziche' fare 2 pow 5000 tentativi,
se si accorge che la statua di Montezuma in scala 1:1 non entra neanche
da sola nel suo zaino, puo' non tentare anche tutte le combinazioni
che la includono e quindi il problema gia' si dimezza (2 pow 4999).
ogni volta che trova una combinazione di oggetti che non entra nello
zaino, se ne libera per non provarla piu'. Questa tecnica porta alla
soluzione sicuramente migliore, ma non si sa in quanti passi, che
potrebbero ancora essere 2 pow N al massimo, ma alcune permutazioni
possono dare il vantaggio di dicotomizzare piu' volte il problema.
Poi ci sono una schiera di algoritmi euristici che non garantiscono
che la soluzione trovata sia la migliore, ma che danno probabilita'
che lo sia, o che sia una delle migliori. Quella che tu hai proposto
e' la forma piu' semplice (greedy 1)
Ciao
Roberto.