SoloCodigo

Te ayudaria, pero no conozco el "famoso" problema

Hola,
trataré de explicar de qué va el problema de la mochila.

Supongamos que tenemos n elementos y cada uno de estos items tiene un peso y un valor. Y tenemos una "mochila" con una capacidad máxima para aguantar cierto peso (llamémosle M). El problema de la mochila tiene dos versiones.
1) La primera es encontrar la mejor forma de combinar estos elemento en la mochila de forma que el peso de la suma de los items no sobrepase el  límite de la mochila y que el valor de la suma de los items sea máximo, dado cierto conjunto de elementos.

2) El segundo es el llamado problema de la mochila fraccionada. Aquí en realidad lo que se puede fraccionar son los items. De modo que podrías meter 'medio' item en la mochila hasta llegar al límite del peso y tratando, de nuevo, de obtener el valor más alto sumando todos los items metidos en la mochila. Por supuesto, si metes una fracción de item su valor también se fracciona. Es decir, si tenemos el item 3 que pesa 6 y cuyo valor es 4 y metemos 1/2 item, entonces el peso será 3, pero el valor será 2 (es decir, 4/2=2). Queda claro ¿no?

Según la teoría de la complejidad computacional este problema es NP-completo. Es decir, no tiene un solución eficiente en términos de complejidad temporal. Para casos sencillos se puede resolver sin problemas, pero para casos con muchos items el coste temporal va creciendo exponencialmente, con lo que en problemas con tallas grandes se hace inviable resolverlo con ningún tipo de algoritmo conocido hasta ahora.

Se suelen emplear algoritmos voraces para su resolución.

Por cierto, si alguno consigue resolverlo con un algoritmo de coste polinómico o lineal que vaya preparándose para empezar a dar conferencias en universidades porque habrá resuelto un dilema computacional que viene desde los años 50. Ya que existe una teoría que dice que si se encuentra solución para algún problema NP-completo, muchos de los demás problemas de la familia NP-completa se podrán resolver aplicando un algoritmo similar. Suerte.

PD: Había en este foro algún matemático que estaba estudiando la rama de computación. Me gustaría comentar sobre la teoría de la complejidad. Es que no recuerdo quién era ni dónde lo he leído. Si me lees, avisa:)

Bueno, manos a la obra (yo tengo una solución algorítmica no implementada).

Saludos.

Por cierto, dije que yo tenía una solución algorítmica. Tengo que aclarar que mi solución no es una solución correcta del todo. Me explico:

El algoritmo que tengo tiene un coste lineal, pero a cambio de esto, no siempre da el mejor resultado para algunos casos, sino que da una soúción aproximadamente óptima. A veces es mejor una solución casi correcta y rápida, que una solución correcta, pero muy lenta. Nada más.

Saludos.

Hola Murciego,

gracias por tu respuesta. Conozco el libro de Brassard y Bratley (ya es un clásico:D junto al Cormen) he estado pensando en comprármelo, quizás lo haga. Con respecto a tu problema de las tablas, ya estuve pensando que sería NP-completo, pero no estaba seguro:P. El caso es que no domino de la teoría de la complejidad, pero algo sé.

Me gustaría si es posible que comentásemos abiertamente en el foro algo de esto, pero podríamos hacerlo en el foro de Algoritmos. En primer lugar me gustaría, si no te importa, que me explicases la diferencia entre un problema de la familia NP y la familia NP-completa (pensaba que eran lo mismo:().
Bueno, ya irán surgiendo cosas.

Un saludo.

Gracias por la explicación, no tengo mucho tiempo ahora, pero ten por seguro que cuando esté más desahogado trataré de plantear algunas otras dudas que me quedan, aunque quizás lo haga en el foro "Diseño de Algoritmos" porque me parece que esto ya no es C. Jejeje.
Un saludo.