6.3. Ejemplos de aplicación.
Problema: maximizar sujeto a con xi= 0, 1
siendo vi = beneficio del objeto i; wi = peso de i; M capacidad máxima.
Características del problema:
- Es un problema de optimización (maximización).
- Sólo nos interesa una solución, la óptima.
- Existirá al menos una solución (no incluir ningún objeto).
Diseño de la solución con backtracking:
- Representación de la solución: Una solución será de la forma (x1, x2, ..., xn), con xi= 0, 1. Se generará un árbol binario de soluciones.
- En cada nivel i, probamos la posibilidad de incluir o no el objeto i.
6.3.1. Problema de la mochila 0/1.