Problema de la mochila

1236 palabras 5 páginas
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

Documentos relacionados

  • Estudio de mercado producto mochilas
    1193 palabras | 5 páginas
  • Problemas De La Multiculturalidad
    1216 palabras | 5 páginas
  • Problema de la investigacion
    3142 palabras | 13 páginas
  • Problemas de la libertad
    799 palabras | 4 páginas
  • Calibracion De Mochila
    855 palabras | 4 páginas
  • Proyecto De Fabricación De Mochilas
    10642 palabras | 43 páginas
  • Problemas de la ética
    1691 palabras | 7 páginas
  • Problemas de la linguistica
    2838 palabras | 12 páginas
  • Problemas de la deforestacion
    2477 palabras | 10 páginas
  • Problema de las llantas
    9334 palabras | 38 páginas