mochila

ufeff


Ejemplo del problema de la mochila: dada una mochila con una capacidad de 15 kg que puedo llenar con cajas de distinto peso y valor, ¿qué cajas elijo de modo de maximizar mis ganancias yno exceder los 15 kg de peso permitidos?









En algoritmia, el problema de la mochila, es un problema de optimización combinatoria, es decir, que busca la mejor solución entre unconjunto de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con unpeso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.

Historia
El problema de la mochila es uno de los 21 problemas NP-completosde Richard Karp, establecidos por el informático teórico en un famoso artículo de 1972.1 Ha sido intensamente estudiado desde mediados del siglo XX y se hace referencia a él en el año 1897, en unartículo de George Mathews Ballard.
Si bien la formulación del problema es sencilla, su resolución es más compleja. Algunos algoritmos existentes pueden resolverlo en la práctica para casos de un grantamaño. Sin embargo, la estructura única del problema, y el hecho de que se presente como un subproblema de otros problemas más generales, lo convierten en un problema frecuente en la investigación.Se caracterizan por manejar una sola restricción y maximación en su función objetivo. Para resolver este método podemos utilizar el método de ramificación y acotamiento para los problemas tipomochila o el método aditivo de Balas.






El problema tipo mochila está formado por los siguientes elementos:
n: número de objetos entre los que se puede elegir.
ai: peso del objeto “i” - serefiere el objeto “i”-ésimo que no es más que una forma de hacer referencia a un objeto cualquiera que pueda ser incluido en la mochila , es decir, ci representa el costo de escoger un objeto, en...