4.3.1. Problema de la mochila.
Ejemplo: n = 3; M = 20
w = (18, 15, 10)
v = (25, 24, 15)
Solución 1: S = (1, 2/15, 0), Valor total = 25 + 24*2/15 = 28.2
Solución 2: S = (0, 2/3, 1), Valor total = 15 + 24*2/3 = 31
Diseño de la solución. Podemos utilizar un algoritmo voraz para resolver el problema.
- Candidatos: Cada uno de los n objetos de partida.
- Función solución: Tendremos una solución si hemos introducido en la mochila el peso máximo M (o si se han acabado los objetos).
- Función seleccionar: Escoger el objeto más prometedor.
- Función factible: Será siempre cierta (podemos añadir trozos de objetos).
- Añadir a la solución: Añadir el objeto entero si cabe en la mochila, o en otro caso la proporción del mismo que quede para completarla.
- Función objetivo: Suma de los beneficios de cada candidato por la proporción seleccionada del mismo.
Queda por definir la función de selección. ¿Qué criterio podemos usar para elegir el objeto más prometedor? ¿Garantiza una solución óptima?