El Problema de la mochila (selección óptima)
Con anterioridad se ha estudiado la posibilidad de encontrar una única solución a un problema y la posibilidad de encontrarlas todas. Pues bien, ahora se trata de encontrar la mejor solución, la solución óptima, de entre todas las soluciones.
Partiendo del esquema que genera todas las soluciones expuesto anteriormente se puede obtener la mejor solución (la solución óptima, seleccionada entre todas las soluciones) si se modifica la instrucción almacenar_solucion por esta otra:
si f(solucion) > f(optimo) entonces optimo <- solucion
siendo f(s) función positiva, optimo es la mejor solucion encontrada hasta el momento, y solucion es una solucion que se está probando.
El problema de la mochila consiste en llenar una mochila con una serie de objetos que tienen una serie de pesos con un valor asociado. Es decir, se dispone de n tipos de objetos y que no hay un número limitado de cada tipo de objeto (si fuera limitado no cambia mucho el problema). Cada tipo i de objeto tiene un peso wi positivo y un valor vi positivo asociados. La mochila tiene una capacidad de peso igual a W. Se trata de llenar la mochila de tal manera que se maximice el valor de los objetos incluidos pero respetando al mismo tiempo la restricción de capacidad. Notar que no es obligatorio que una solución óptima llegue al límite de capacidad de la mochila.
Ejemplo: se supondrá:
n = 4
W = 8
w() = 2, 3, 4, 5
v() = 3, 5, 6, 10
Es decir, hay 4 tipos de objetos y la mochila tiene una capacidad de 8. Los pesos varían entre 2 y 5, y los valores relacionados varían entre 3 y 10.
Una solución no óptima de valor 12 se obtiene introduciendo cuatro objetos de peso 2, o 2 de peso 4. Otra solución no óptima de valor 13 se obtiene introduciendo 2 objetos de peso 3 y 1 objeto de peso 2. ¿Cuál es la solución óptima?.
A continuación se muestra una solución al problema, variante del esquema para obtener todas las soluciones.
void mochila(int i, int r, int solucion, int *optimo)
{
int k;
for (k = i; k < n; k++) {
if (peso[k] <= r) {
mochila(k, r - peso[k], solucion + valor[k], optimo);
if (solucion + valor[k] > *optimo) *optimo = solucion+valor[k];
}
}
}
Dicho procedimiento puede ser ejecutado de esta manera, siendo n, W, peso y valor variables globales para simplificar el programa:
n = 4,
W = 8,
peso[] = {2,3,4,5},
valor[] = {3,5,6,10},
optimo = 0;
...
mochila(0, W, 0, &optimo);
Observar que la solución óptima se obtiene independientemente de la forma en que se ordenen los objetos.
El de Greedy (http://decsai.ugr.es/~jhg/TA/Greedy0405.pdf) |
