Knapsack Problem - Gutierrez Almendra

Knapsack Problem

(Problema de la mochila)

Análisis Numérico 2021

Profesora : Moreno Verónica Alumna: Gutierrez Almendra

Knapsack problem

Es un problema de optimización combinatoria. Trata de buscar la mejor solución entre un conjunto finito de posibles soluciones al 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 un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.

Planteo del problema

El problema de la mochila es un problema simple de entender: hay una persona que tiene una mochila con una cierta capacidad y tiene que elegir que elementos pondrá en ella. Cada uno de los elementos tiene un peso y aporta un beneficio. El objetivo de la persona es elegir los elementos que le permitan maximizar el beneficio sin excederse de la capacidad permitida.

Veamos un ejemplo

Si contaramos con 4 productos, para saber cual es la mejor solución podríamos probar las 24 = 16 posibilidades. El 2 se desprende del hecho de que cada decisión es incluir o no al producto y el 4 de la cantidad de productos. 16 posibilidades es un número manejable, sin embargo, si la cantidad de elementos por ejemplo ascendiera a 20, tendríamos que analizar nada más y nada menos que 220 = 1,048,576 posibilidades

Expresión en términos matemáticos

• Los objetos están numerados por el índice i variando de 1 a n.
• Los números wi y vi representan el peso y el valor del número i.
• La capacidad de la mochila se denomina en esta fórmula W.

Hay muchas manera de llenar la mochila, debemos decidir para cada objeto si lo metemos en la mochila o no, pudiendo utilizar el código binario que cuando xi = 1, agregamos el objeto en la mochila, o cuando xi = 0 , queda afuera. Siendo xi un conjunto de los objetos disponibles.

Solución para la resolución del problema

Hay varios algoritmos que se pueden implementar para la resolución del problema de la mochila. Algunos de ellos son:

• Fuerza bruta
• Algoritmo codicioso, relación costo/peso
• Programación Dinámica
• Branch and Bound
• Etc.

En esta presentación nos dedicaremos al método de Branch and Bound

Optimización Discreta

Basicamente la optimización trata de encontrar la mejor solución entre todas las soluciones posibles para resolver un problema.

Branch and Bound

Este algoritmo se suele utilizar para resolver problemas de optimización

Branch and Bound

Para resolver este algoritmo, deberíamos conocer un límite del subárbol de la mejor solución posible asociado con cada nodo. Si lo mejor en el subárbol es peor que el mejor valor que tenemos actualmente, podemos simplemente ignorar el nodo y sus subárboles. Entonces, vamos a calcular el la mejor solución para cada nodo y compararemos el mismo con la mejor solución actual antes de explorar el nodo

Es una técnica muy útil para buscar una solución, pero en el peor de los casos, necesitamos calcular el árbol completo. En el mejor de los casos, solo necesitamos calcular un camino a través del árbol y el resto se descarta.

Resolución del algoritmo (Branch and Bound)

1. Inicializar el beneficio máximo
2. Crear una cola vacía
3. Crear un nodo auxiliar del árbol. El costo y el peso del nodo auxiliar son 0.
4. Mientras la cola no esté vacía:

- Extraer un elemento de la cola- Calcular el beneficio del nodo del nivel siguiente. Si el beneficio es mayor al que calculamos, debemos actualizar el valor. - Calcular el límite del nodo del siguiente nivel. Si el limite es mayor que nuestro beneficio, agregar el siguiente nodo a la cola.

Ilustración a modo de ejemplo

Conclusion

El tiempo de ejecución de este algoritmo depende de: - El número de nodos recorridos - El tiempo empleado en cada nodo (tiempo necesario para hacer las estimaciones de costo y gestionar la lista de nodos en función de la estrategia de ramificación). Maximizamos el beneficio que obtenemos al incluir un objeto en la mochila.

Bibliografía

1. https://es.wikipedia.org/wiki/Problema_de_la_mochila

2. Teoría de la complejidad computacional. http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_complejidad_computacional

3. https://www.geeksforgeeks.org/

4. https://repositorio.uc.cl/xmlui/bitstream/handle/11534/21971/Morales_Ignacio.pdfhttps://repositorio.uc.cl/xmlui/bitstream/handle/11534/21971/Morales_Ignacio.pdf

5. https://drive.google.com/drive/u/0/folders/1OUBi81ecqtNxCFeRsMb-9rc1ypuyjtMXhttps://drive.google.com/drive/u/0/folders/1OUBi81ecqtNxCFeRsMb-9rc1ypuyjtMX

6. https://128mots.com/index.php/2021/03/29/problema-de-mochila-algoritmo-en-python-problema-de-mochila/https://128mots.com/index.php/2021/03/29/problema-de-mochila-algoritmo-en-python-problema-de-mochila/

7. https://www.gatevidyalay.com/tag/0-1-knapsack-problem-using-branch-and-bound/

8. https://www.programmersought.com/article/94102535329/

9. https://elvex.ugr.es/decsai/algorithms/slides/5%20Branch%20and%20Bound.pdf