Math
Zaino: avidità contro la tabella
Scegli carichi numerati entro un limite di peso. Confronta con l’avido e l’ottimo, apri una cella e risali alla scelta ottima.
Cosa succede
Scegli carichi numerati entro un limite di peso. Confronta con l’avido e l’ottimo, apri una cella e risali alla scelta ottima. T(i,c): miglior valore dei primi i oggetti con capacità c. Clicca una cella: blu salta, verde prende. Le frecce cambiano pagina. w = peso, v = valore. Le dimensioni sono decorative; conta solo il peso totale. Il limite frazionario permette di dividere gli oggetti. È un limite superiore, non una scelta ammissibile 0/1.
Equazioni del modulo
Equazioni
0/1: sum(w_i x_i) <= W; max sum(v_i x_i), con x_i in {0,1}
T(0,c) = 0
w_i > c: T(i,c) = T(i-1,c)
w_i <= c: T(i,c) = max(T(i-1,c), v_i + T(i-1,c-w_i))
v_i/w_i ↓; i ↑
F_greedy <= F_0/1 <= F_fractional
V_single = max({0} ∪ {v_i : w_i <= W})
max(F_greedy, V_single) >= F_0/1 / 2
N_DP = n*W; N_subsets = 2^n
