El Problema De La Mochila
El problema de la mochila consiste en llenar una mochila con una serie de objetos que tienen una serie de pesos con un beneficio 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 Pi y un valor Bi beneficio asociado. La mochila tiene una capacidad de peso igual a M. 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. El objetivo es llenar la mochila, de capacidad M, de manera …ver más…

4. Construcción de la solución óptima haciendo uso de la información contenida en la tabla anterior.

Problema de la Mochila 0/1 Programación Dinámica

for(int i=1;i<=n;i++) { V[i][0]=0; for( int j=1;j<=M;j++) { V[0][j]=0; if(j-p[i]>=0) V[i][j]= Max(V[i-1][j], b[i] + V[i-1][j-p[i]]); else V[i][j]=V[i-1][j]; } } int j=6; for(int i=n;i>=1;i--) { if(V[i][j]==V[i-1][j]) x[i-1]=0; else { x[i-1]=1; j =j-p[i]; } }
Función de Tiempo de ejecución: i=1n(j=1M1)+n= i=1nM=n*M+n

Tn=nM+1 → Tn∈O(n.M)

Programación Vuelta Atrás (Backtracking) Es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en los años 1950s. En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede