Analisis Del Algoritmo Backtrack Aplicado A El Problema De La Mochila

TALLER DE ANALISIS (ALGORITMOS BACKTRACKING)

1) Realizar un análisis de la solución del problema de la mochila utilizando el enfoque backtracking.
Descripción del problema:
Dados n elementose1, e2, ..., en con pesos p1, p2, ..., pn y beneficios b1, b2, ..., bn, y dada una mochila capaz de albergar hasta un máximo peso M (capacidad de la mochila), queremos encontrar cuáles de los nelementos hemos de introducir en la mochila de forma que la suma de los beneficios de los elementos escogidos sea máxima, sujeto a la restricción de que tales elementos no pueden superar la capacidadde la mochila
Es un problema de optimización (maximización).
Sólo nos interesa una solución, la óptima.
Existirá al menos una solución
La solución
Éste es uno de los problemas cuya resolución mássencilla se obtiene utilizando la técnica de Vuelta Atrás, puesto que basta expresar la solución al problema como una n-tupla de valores X = [x1, x2, ..., xn] donde xi tomará los valores 1 ó 0dependiendo de que el i-ésimo objeto sea introducido o no. El árbol de expansión resultante es, por tanto, trivial.
Sin embargo, y puesto que se trata de un problema de optimización, podemos aplicaruna poda para eliminar aquellos nodos que no conduzcan a una solución óptima. Para ello vamos utilizaremos una función (Cota) que es la que va a permitir realizar la poda del árbol de expansión paraaquellos nodos que no lleven a la solución óptima. Para ello vamos a considerar que los elementos iniciales están todos ordenados de forma decreciente por su ratio beneficio/peso. De esta forma,supongamos que nos encontramos en el paso k-ésimo, y que disponemos de un beneficio acumulado
Para calcular el valor máximo que podríamos alcanzar con ese nodo (BM), vamos a suponer que rellenáramos elresto de la mochila con el mejor de los elementos que nos quedan por analizar. Como los tenemos dispuestos en orden decreciente de ratio beneficio/peso, este mejor elemento será el siguiente (k+1)....