Programación General > C/C++
Re: problema de la mochila
gatubela:
necesito que me ayuden con el famoso problema de la mochila, el algoritmo de fuerza bruta lo tengo hecho, pero por lo que he averiguado parece que es un problema NP-completo, con grafos. gracias
avefenix:
Te ayudaria, pero no conozco el "famoso" problema :P
chuntaro:
si me dices el problema???? te garantizo resolverlo!!!
con grafos o , pseudo, codg. o como quieras!!!!
De Profundiis:
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.
r3dsk1:
Uhhao parece un reto interesante para todos,suerte a todos que lo intenten.
Saludos.
Navegación
[#] Página Siguiente
Ir a la versión completa