6.3.1. Problema de la mochila 0/1.
Función Criterio (nivel, s, v_act, w_act, v_max).
v_estimado:= v_act + ?MochilaVoraz (nivel+1, M - w_act)?;
Devolver v_estimado > v_max;
Modificación en el algoritmo de backtracking.
while not MasHermanos (nivel, s) or
not Criterio (nivel, s, v_act, w_act, v_max) do
Se eliminan nodos a costa de aumentar el tiempo de ejecución de la función Criterio. ¿Cuál será el tiempo de ejecución total?
Suponemos todos los objetos ordenados por vi/wi.
Tiempo de la función Criterio en el nivel i (en el peor caso) = 1 + Tiempo de la función MochilaVoraz = 1 + n - i.
Idea intuitiva. Tiempo en el peor caso (suponiendo todos los nodos): Número de nodos O(2n) * Tiempo de cada nodo (función criterio) O(n).