7.3.1. Problema de la mochila 0/1.
Cálculo de cotas:
- Cota inferior: Beneficio que se obtendría incluyendo sólo los objetos incluidos hasta ese nodo.
- Estimación del beneficio: A la solución actual, sumar el beneficio de incluir los objetos enteros que quepan, utilizando avance rápido. Suponemos que los objetos están ordenados por orden decreciente de vi/wi.
- Cota superior: Resolver el problema de la mochila no 0/1 a partir de ese nodo (con un algoritmo voraz), y quedarse con la parte entera. (Es la misma que la usada en backtracking.)
Ejemplo. n = 4, M = 7, v = (2, 3, 4, 5), w = (1, 2, 3, 4)
Nodo actual: (1, 1) (1, 2)
Hijos: (1, 1, 0), (1, 1, 1) (1, 2, 3), (1, 2, 4)
Cota inferior: CI = v1 + v2 = 2 + 3 = 5
Estimación del beneficio: EB = CI + v3 = 5 + 4 = 9
Cota superior: CS = CI + ?MochilaVoraz (3, 4)? = 5 + ?4 + 5/4? = 10