Definición - ¿Qué significa problema de mochila?
El problema de la mochila es un problema de optimización que se utiliza para ilustrar tanto el problema como la solución. Deriva su nombre de un escenario en el que uno está limitado en el número de artículos que se pueden colocar dentro de una mochila de tamaño fijo. Dado un conjunto de artículos con pesos y valores específicos, el objetivo es obtener el mayor valor posible en la mochila dada la restricción de peso de la mochila.
Techinfo explica el problema de la mochila
El problema de la mochila es un ejemplo de un problema de optimización combinacional, un tema en matemáticas e informática sobre cómo encontrar el objeto óptimo entre un conjunto de objetos. Este es un problema que se ha estudiado durante más de un siglo y es un problema de ejemplo de uso común en la optimización combinatoria, donde existe la necesidad de un objeto óptimo o una solución finita donde no es posible una búsqueda exhaustiva. El problema se puede encontrar en escenarios del mundo real como la asignación de recursos en restricciones financieras o incluso en la selección de inversiones y carteras. También se puede encontrar en campos como las matemáticas aplicadas, la teoría de la complejidad, la criptografía, la combinatoria y la informática. Es sin duda el problema más importante de la logística.
En el problema de la mochila, los artículos dados tienen dos atributos como mínimo: el valor de un artículo, que afecta su importancia, y el peso o volumen de un artículo, que es su aspecto de limitación. Como no es posible realizar una búsqueda exhaustiva, se pueden dividir los problemas en subproblemas más pequeños y ejecutarlos de forma recursiva. Esto se denomina subestructura óptima. Se trata de un solo artículo a la vez y el peso actual todavía está disponible en la mochila. El solucionador de problemas solo necesita decidir si tomar el artículo o no en función del peso que aún se puede aceptar. Sin embargo, si es un programa, el recálculo no es independiente y causaría problemas. Aquí es donde se pueden aplicar las técnicas de programación dinámica. Las soluciones para cada subproblema se almacenan de modo que el cálculo solo deba realizarse una vez.