Algoritmia - El problema de la mochila

Hola!

Tengo un problema el cual se resuelve con el Algoritmo del
Problema de la Mochila sin fraccionamiento, he implementado
el algoritmo (Mochila1, Mochila2 y Mochila3)
que se encuentra en la siguiente direccion
http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf

Sin embargo al ser un problema NP Completo, es intratable,
para una entrada de 30 elementos este algoritmo tarda horas en dar el resultado
(cualquiera de los 3 algoritmos).

Me entere que hay un algoritmo paralelo (algo del hipercubo) el cual
resuelve el mismo problema quiza no con la exactitud del
algoritmo original pero quiza aceptable.

Si alguien me puede pasar este algoritmo o cualquier información
al respecto se lo agradecere.

Saludos

Horacio, entiendo que estás buscando una solución más eficiente para el problema de la mochila sin fraccionamiento, dado que la implementación actual tarda mucho tiempo en ejecutarse para instancias grandes.

Respecto a un algoritmo paralelo, no hay un algoritmo específico universal que sea "el" algoritmo paralelo para este problema. La paralelización puede realizarse de diversas formas dependiendo del contexto y de las características del problema.

Sin embargo, puedo sugerirte algunas ideas generales sobre cómo podrías abordar la paralelización de este problema:

1. División de tareas: Puedes dividir el conjunto de elementos en subconjuntos más pequeños y asignar cada subconjunto a un hilo o proceso diferente para que procesen de manera independiente. Luego, combinar los resultados obtenidos por cada subconjunto.

2. Algoritmo genético paralelo: Los algoritmos genéticos son métodos de optimización que pueden paralelizarse eficientemente. Puedes considerar implementar un algoritmo genético paralelo para abordar el problema de la mochila.

3. Exploración paralela del espacio de soluciones: Si bien algunos algoritmos no paralelos pueden ser transformados para funcionar en entornos paralelos, también puedes explorar soluciones en paralelo. Por ejemplo, al probar diferentes combinaciones de elementos en diferentes hilos.

Es importante mencionar que, aunque la paralelización puede mejorar el rendimiento en algunos casos, la complejidad del problema de la mochila sin fraccionamiento implica que no siempre se puede garantizar una mejora significativa.

Si buscas algoritmos específicos o implementaciones paralelas, te recomendaría explorar la literatura académica, repositorios de código abierto, o comunidades en línea especializadas en algoritmos y optimización para encontrar recursos específicos.