Math
Mochila: la codicia contra la tabla
Elige objetos numerados con un límite de peso. Compara con el voraz y el óptimo, abre una celda y sigue el camino de vuelta a la selección óptima.
Qué ocurre
Elige objetos numerados con un límite de peso. Compara con el voraz y el óptimo, abre una celda y sigue el camino de vuelta a la selección óptima. T(i,c): mejor valor de los primeros i objetos con capacidad c. Pulsa una celda: azul omite, verde toma. Las flechas pasan páginas. w = peso, v = valor. El tamaño es decorativo; solo se limita el peso total. La cota fraccionaria permite dividir objetos. Es una cota superior, no una selección válida del problema 0/1.
Ecuaciones del módulo
Ecuaciones
mochila 0/1: sum(w_i x_i) <= W; max sum(v_i x_i), x_i en {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
