Algoritmo approssimato per lo zaino 0-1

antony881
Avrei un problema sulla comprensione dell'algoritmo approssimato per la suluzione dello zaino 0-1. In pratica quest' algoritmo divide tutti i valori per una quantità fissata $ theta = epsilon / n * vmax $ , dove vmax sarebbe il profitto massimo quindi i profitti $v_i$ sono ridotti in : tetto di $ v_i/theta$ ed inoltre viene utilizzato anche un altro valore cioè : (tetto di $ v_i/theta $) * $theta$, ed esegue l'algoritmo di programmazione dinamica con i valori dei profitti ridotti . La mia questione è perchè viene utilizzato anche l'altro valore cioè : (tetto di $ v_i/theta $) * $theta$, quel è il suo significato?

grazie a tutti

Risposte
hamming_burst
Ciao,
non mi è molto chiara la tua notazione, la hai presa da qualche libro o dispensa?

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.