04/02/12

Problema dello zaino - Wikipedia

Problema dello zainoDa Wikipedia, l'enciclopedia hbera.TIProblema dello zaino, detto anche Knapsack problem, un

problema di ottirnizzazione combnatoria posto nel modoseguente: sia dato uno zaino che possa sopportare un determinato peso. Siano dati inoltre N oggetti, ognuno dei quali caratterizzato da un peso e un valore. TIproblema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il maggiore valore senza eccedere nel peso sostenibile dallo zaino stesso.Indice

7

In questo caso, la soluzione di mettere

1 Introduzione 2 Soluzione problema dello zaino senza limiti 3 Soluzione problema dello zaino 0-14

nello zaino tre scatole gialle e tre grigie

Algoritmo Greedy 5 Rilassamento continuo 6 Bibliografia

IntroduzioneIl problema espresso in maniera pi formale diventa: ognuno degli N oggetti possiede un peso wi e un valore Ci; 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 Xi. La funzione obiettivo :

rnax ZI vincoli:

=

Li=l

.l'-l

Ci . X'i

L ui, .i=l-t>

}\l

Xi

T[i] THEN T[i] ENDFOR ENDFOR OUTPUT T[e]

T[i -

Pj]

+ Vj

Dati i valori del vettore T, gli oggetti da inserire nello zaino per ottenere il valore T[ C] possono essere facilmente individuati in tempo O(C) procedendo dall'ultima verso la prima cella del vettore e spendendo tempo 0(1) per cella. OGGETTI: INPUT l'intero C, i pesi PI, .. -P. i valori VI, ... Vn e il vettore T OUTPUT l'array SOL (di dimensione n) tale che SOL[i] il numero di oggetti di tipo i presi dalla soluzione capacita t- C FaR i = l TO n DO SOL[i] t- O WHILE capacita> Pi AND T[capacita - Pi] = T[capacita] - Vi DOSOL

[i]

tt-

SOL[i]

+l

capacita ENDWHILE ENDFOR RETURN SOL

capacita - Pi