Programación dinámica: el problema de knapsack
11/03/2018
Los algoritmos nos ayudan a resolver problemas. Hay muchas maneras de diseñarlos, un método que no conocía hasta hace poco y que me ha resultado muy interesante conocer es la programación dinámica. La idea fundamental de la programación dinámica es dividir el problema en subproblemas y posteriormente calcular una única vez cada subproblema. Existen dos acercamientos: top-down y bottom-up. La programación dinámica nos permite resolver problemas más rápidamente que con fuerza bruta, gastando a cambio mucha más memoria del ordenador.
Como explicado así, es un poco abstracto, vamos a intentar resolver un problemas clásico de programación dinámica, el problema de knapsack (o de la mochila).
Imagina que tenemos una mochila con capacidad para 10 kg. Tenemos 400 elementos para meter en la bolsa, cada uno de ellos con un peso y un valor. ¿Cuál es el valor máximo que podemos llevar en la bolsa?
Este problema parece muy complicado de resolver. Quizá lo único que se nos ocurra es probar todas las combinaciones posibles de elementos, descartar las combinaciones que exceden el peso que puede llevar la mochila y de las restantes quedarnos con el máximo. Funcionaría, pero sería extremadamente lento.
Como cada elemento puede estar o no estar en la mochila, y son 400, las combinaciones son 2⁴⁰⁰=2582249878086908589655919172003011874329705792829223512830659356540647622016841194629645353280137831435903171972747493376. Excesivo.
Otra idea que podría surgir es backtracking. Básicamente recorreríamos todos los elementos posibles en forma de árbol, pero en cuanto veamos que ya no entran más elementos cortamos la búsqueda por esa rama y tomamos otra. Mejoraría el rendimiento, pero no es tampoco lo mejor que se podría hacer.
La solución es usar programación dinámica, vamos a aplicar el enfoque top-down. Lo primero es expresar la solución de forma recursiva.
La función mochila se define como el valor máximo que puede llevar una mochila, con N elementos a elegir y con una capacidad C.
El primer if es la solución óptima, que es trivial si sabemos que ya no quedan elementos por revisar o si la capacidad que queda en la mochila es cero. El elif y else siguientes nos dan las soluciones óptimas también, pero de forma recursiva. En el primer caso, si el elemento es demasiado grande, solo se puede continuar probando con otro elemento, en el otro caso, hacemos los dos cálculos. Miramos si obtenemos más valor metiendo el elemento o sin meterlo y devolvemos el máximo. Este es el primer paso, básicamente es backtracking lo que hemos hecho.
Si bien la solución funcionaba, podemos darnos cuenta de que el ordenador iba a calcular muchas veces lo mismo. En programación dinámica no se calcula nunca nada más de una vez. Una solución sencilla para lograrlo es aplicar memoización, es decir, mantenemos un historial de llamadas a la función con argumentos. Piensa en ello como una caché.
En Python existe desde 3.2 en el módulo functools una caché que cumple lo necesario para memoizar.
Este ligero cambio mejora drásticamente el rendimiento, haciendo que se calcule de forma casi instantánea (mientras que la otra versión tarda minutos).
Python no es un lenguaje que optimice las llamadas recursivas. Tampoco lo es Java. Ciertamente, en muchos lenguajes hacer demasiadas llamadas recursivas provoca un Stack Overflow. Ante esto se puede reescribir el algoritmo para que sea un bucle (el enfoque bottom-up) o se puede reescribir en un lenguaje que optimice las llamadas recursivas como Haskell o Lisp.
La solución bottom-up de este problema (usando una matriz) sería la siguiente:
Esta versión es más rápida y no tiene el problema del límite de recursividad, pero es menos legible.
(en la esquina encontraremos la solución óptima)
Como explicado así, es un poco abstracto, vamos a intentar resolver un problemas clásico de programación dinámica, el problema de knapsack (o de la mochila).
Problema de Knapsack
Imagina que tenemos una mochila con capacidad para 10 kg. Tenemos 400 elementos para meter en la bolsa, cada uno de ellos con un peso y un valor. ¿Cuál es el valor máximo que podemos llevar en la bolsa?
Este problema parece muy complicado de resolver. Quizá lo único que se nos ocurra es probar todas las combinaciones posibles de elementos, descartar las combinaciones que exceden el peso que puede llevar la mochila y de las restantes quedarnos con el máximo. Funcionaría, pero sería extremadamente lento.
Como cada elemento puede estar o no estar en la mochila, y son 400, las combinaciones son 2⁴⁰⁰=2582249878086908589655919172003011874329705792829223512830659356540647622016841194629645353280137831435903171972747493376. Excesivo.
Otra idea que podría surgir es backtracking. Básicamente recorreríamos todos los elementos posibles en forma de árbol, pero en cuanto veamos que ya no entran más elementos cortamos la búsqueda por esa rama y tomamos otra. Mejoraría el rendimiento, pero no es tampoco lo mejor que se podría hacer.
La solución es usar programación dinámica, vamos a aplicar el enfoque top-down. Lo primero es expresar la solución de forma recursiva.
La función mochila se define como el valor máximo que puede llevar una mochila, con N elementos a elegir y con una capacidad C.
def mochila(n,c):
if n == 0 or c == 0:
# solucion optima para cuando no quedan elementos o la capacidad disponible es 0
return 0
elif datos[n].peso > c:
# no metemos el elemento
return mochila(n-1,c)
else:
#sin meter el elemento
a = mochila(n-1,c)
# metiendo el elemento
b = datos[n].valor + mochila(n-1,c-datos[n].peso)
return max(a,b)
El primer if es la solución óptima, que es trivial si sabemos que ya no quedan elementos por revisar o si la capacidad que queda en la mochila es cero. El elif y else siguientes nos dan las soluciones óptimas también, pero de forma recursiva. En el primer caso, si el elemento es demasiado grande, solo se puede continuar probando con otro elemento, en el otro caso, hacemos los dos cálculos. Miramos si obtenemos más valor metiendo el elemento o sin meterlo y devolvemos el máximo. Este es el primer paso, básicamente es backtracking lo que hemos hecho.
Memoizar
Si bien la solución funcionaba, podemos darnos cuenta de que el ordenador iba a calcular muchas veces lo mismo. En programación dinámica no se calcula nunca nada más de una vez. Una solución sencilla para lograrlo es aplicar memoización, es decir, mantenemos un historial de llamadas a la función con argumentos. Piensa en ello como una caché.
En Python existe desde 3.2 en el módulo functools una caché que cumple lo necesario para memoizar.
import functools
@functools.lru_cache(maxsize=None)
def mochila(n,c):
if n == 0 or c == 0:
# solucion optima para cuando no quedan elementos o la capacidad disponible es 0
return 0
elif datos[n].peso > c:
# no metemos el elemento
return mochila(n-1,c)
else:
#sin meter el elemento
a = mochila(n-1,c)
# metiendo el elemento
b = datos[n].valor + mochila(n-1,c-datos[n].peso)
return max(a,b)
Este ligero cambio mejora drásticamente el rendimiento, haciendo que se calcule de forma casi instantánea (mientras que la otra versión tarda minutos).
Recursividad
Python no es un lenguaje que optimice las llamadas recursivas. Tampoco lo es Java. Ciertamente, en muchos lenguajes hacer demasiadas llamadas recursivas provoca un Stack Overflow. Ante esto se puede reescribir el algoritmo para que sea un bucle (el enfoque bottom-up) o se puede reescribir en un lenguaje que optimice las llamadas recursivas como Haskell o Lisp.
La solución bottom-up de este problema (usando una matriz) sería la siguiente:
V = list()
def mochila_two(n,c):
for x in range(n):
V.append([])
for y in range(c+1):
V[x].append(0)
for i in range(n):
for w in range(c+1):
if datos[i].peso <= w:
V[i][w] = max(V[i-1][w],datos[i].valor+V[i-1][w-datos[i].peso])
else:
V[i][w] = V[i-1][w]
return V[n-1][c]
Esta versión es más rápida y no tiene el problema del límite de recursividad, pero es menos legible.
(en la esquina encontraremos la solución óptima)