La primera aplicación trata de paralelizar el problema de la mochila, conocido como el Knapsack problem 0/1, que trata de maximizar una función enlazada a ciertos parámetros. Básicamente se pide llenar un contenedor (como una mochila) de objetos que tienen un peso w y un valor de v , de tal manera que se maximice el valor dentro del contenedor sin sobrepasar su peso maximo W. Gráficamente se puede observar asi :
En este caso los objetos, con (v, w), son (4, 12), (2, 1), (10, 4), (1, 1) y (2, 2) y el contenedor tiene como peso máximo W = 15, entonces la solución óptima seria:
objeto valor peso pertenece
1 4 12 false
2 2 1 true
3 10 4 true
4 1 1 true
5 2 2 true
En el siguiente informe veremos el trabajo completo sobre este problema y su implementación paralela. Al final de esta pagina, encontrarás los links de descarga, tanto para el pdf como para el código fuente en C usando OpenMP.
Aplicación I
Programación dinámica aplicado al problema de la mochila 0/1 con enfoque paralelo
