6.3.1. Problema de la mochila 0/1.
Orden de complejidad del algoritmo: Número de nodos generado= 2n+1-1. El algoritmo es de O(2n).
Problema: En el ejemplo, se generan todos los nodos posibles. La función Criterio es siempre cierta (excepto para algunos nodos hoja).
Solución: Intentar eliminar algunos nodos del árbol de soluciones, con una función Criterio más restrictiva.
- Para cada nodo, hacer una estimación del máximo beneficio que se podría obtener a partir del mismo.
- Si es menor que el mayor beneficio de una solución anterior (v_max) entonces rechazar ese nodo y sus descendientes.
¿Cómo podemos calcular una cota superior del beneficio que se puede obtener a partir de un nodo, es decir a partir de (x1, ..., xk)? La estimación debe poder realizarse de forma rápida.
La estimación del beneficio para el nivel y nodo actual será:
v_estimado:= v_act + Estimacion (k + 1, M - w_act);
Estimacion (k, Q): Estimar una cota superior para el problema de la mochila 0/1, usando los objetos k..n, con capacidad máxima Q.