Foros del Web » Programando para Internet » Python »

[Aporte] Problema de la mochila

 Estas en el tema de [Aporte] Problema de la mochila en el foro de Python en Foros del Web. Hoy les voy a enseñar el problema de mochila 0-1. El problema de la mochila siempre se explica mejor por medio de un ejemplo. Supongan ...
  #1 (permalink)  
Antiguo 10/12/2011, 13:07
Avatar de razpeitia
Moderador
  
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 19 años, 1 mes
Puntos: 1360
[Aporte] Problema de la mochila
Hoy les voy a enseñar el problema de mochila 0-1.

El problema de la mochila siempre se explica mejor por medio de un ejemplo.
Supongan que son un ladrón que acaba de entrar a una bóveda, para esto ustedes solo llevan consigo una mochila que tiene una capacidad limitada, en este caso de c cantidad de kilos. Ahora ante sus ojos se encuentran con n objetos cada uno con un valor v y un peso p.

Lamentablemente usted no puede llevar todos los objetos así que debe de escoger aquella combinación de objetos tal que la suma de sus valores sea máxima y la suma de sus pesos no rebase la capacidad de la mochila.

Una definición rigurosa la pueden leer en wikipedia.

Vamos a ver ejemplo mas simple de como resolver esto:

Antes de empezar definamos nuestra clase Item
Código Python: 
Ver original
  1. class Item:
  2.     def __init__(self, value, weight):
  3.         self.value = value
  4.         self.weight = weight
  5.  
  6.     def __str__(self):
  7.         return "Value: %d - Weight: %d" % (self.value, self.weight)
  8.     
  9.     def __repr__(self):
  10.         return self.__str__()
No es mas que una simple clase llamada "Item" que contiene un valor y un peso. Ademas tiene una forma bonita para convertirlo a un string.

Los datos con los que vamos a con los que vamos a estar trabajando son los siguientes:
Código Python: 
Ver original
  1. items = [Item(4, 12),
  2.          Item(2, 2),
  3.          Item(2, 1),
  4.          Item(1, 1),
  5.          Item(10, 4),
  6.         ]

Fuerza bruta

Ahora la manera mas directa de resolver esto por por fuerza bruta esto es generar todas las combinaciones y ver que combinación o combinaciones nos convienen mas. De momento solo mostrare como obtener la mayor suma de los valores de los items sin sobre pasar la capacidad de la mochila.

Código Python: 
Ver original
  1. c = 0
  2. def ks(index, weight):
  3.     global items
  4.     global c
  5.     c += 1
  6.  
  7.     if index >= len(items):
  8.         return 0
  9.  
  10.     item = items[index]
  11.  
  12.     if item.weight > weight:
  13.         return ks(index + 1, weight)
  14.     else:
  15.         return max(ks(index + 1, weight),
  16.                    ks(index + 1, weight - item.weight) + item.value)
  17.  
  18. print "Max sum: %d" % (ks(0, 20),)
  19. print "Iterations %d" % (c,)
  20. print

Linea 1: Es solo un contador de llamadas a función

Linea 2: Es la definición de nuestra función, que toma como parámetros un indice "index" y un peso o capacidad de la mochila.

Linea 3 y 4: Pones al alcance variables globales como "items" y "c"

Linea 5: Incrementamos el contador de llamadas

Linea 7 y 8: Checamos si el indice se encuentra dentro del limite de la lista de items, si no entonces no podemos agarrar ningún item y regresamos 0.

Linea 10: Ponemos item como el item en la posición del indice dado.

Linea 12 y 16: Verificamos si podemos poner el item dentro de la mochila, si no podemos entonces simplemente pasamos al siguiente item. Si podemos meter el item a la mochila entonces podemos agarrar 2 caminos meter el item y esto involucra varias cosas primero la capacidad de mochila se reduce, segundo el valor de los items agarrados hasta el momento aumenta pero también puede que sea una mala decisión y que el espacio que ocupa ese item puede ser usado por otro u otros items que sumen un mayor valor. Como nosotros no sabes cual es el mejor camino entonces tomamos los 2 caminos y simplemente agarramos el que camino que tenga mayor valor.

El resto de las lineas solo imprime la suma máxima, suponiendo que la capacidad de la mochila es de 20kg y despues imprime cuantas veces se llamo a esa función.

La complejidad de este algoritmo es de O(2^n) donde n es la cantidad de items, entonces se puede decir que este algoritmo tiene una complejidad exponencial.

Si graficamos el árbol de llamadas a función nos vamos a topar con que muchas llamadas a función se repiten, después de todo si llamamos 2^n veces a la función pero nuestro espacio de parámetros es de tan solo n * m donde n es el numero de items y m es el peso entonces podemos concluir que muchas llamadas a función se repetirán.

Programación dinámica (recursiva)

Entonces para optimizar este algoritmo vamos a guardar las llamadas a función que hagamos con una técnica llamada memoization.

Entonces nuestro algoritmo queda mas o menos de la siguiente manera:
Código Python: 
Ver original
  1. c = 0
  2. mem = {}
  3. def ks(index, weight):
  4.     global items
  5.     global c
  6.     global mem
  7.     c += 1
  8.  
  9.     case = (index, weight)
  10.     if case in mem:
  11.         return mem[case]
  12.  
  13.  
  14.     if index >= len(items):
  15.         mem[case] = 0
  16.         return mem[case]
  17.  
  18.     item = items[index]
  19.     grab_case = (index + 1, weight - item.weight)
  20.     no_grab_case = (index + 1, weight)
  21.  
  22.     if item.weight > weight:
  23.         mem[case] = ks(*no_grab_case)
  24.         return mem[case]
  25.     else:
  26.         if no_grab_case not in mem:
  27.             mem[no_grab_case] = ks(index + 1, weight)
  28.         if grab_case not in mem:
  29.             mem[grab_case] = ks(index + 1, weight - item.weight) + item.value
  30.         mem[case] = max(mem[grab_case], mem[no_grab_case])
  31.         return mem[case]
  32.  
  33. print "Max sum: %d" % (ks(0, 20),)
  34. print "Iterations %d" % (c,)
  35. print
La lógica sigue siendo la misma. Lo único que cambia es que añadi memoization para cada llamada a función.
Y definí tuplas como case que indica el caso actual, grab_case el caso donde agarramos el item y no_grab_case el caso donde no agarramos el item.

Si se fijan el resultado es el mismo, pero con menos llamadas a función. La complejidad de este algoritmo se ha reducido a O(n * m)

Programación dinámica (Iterativa)

Ahora para saber que items tenemos que tomar es necesario mantener una matriz de items que hemos tomado, en la fila va el item y en las columnas el paso y ademas tenemos que tener otra matriz con todas los valores de las llamadas a función.

Código Python: 
Ver original
  1. def ks(items, weight):
  2.     mem = [[0 for j in xrange(weight + 1)]
  3.            for i in xrange(len(items) + 1)]
  4.     
  5.     grab = [[0 for j in xrange(weight + 1)]
  6.            for i in xrange(len(items) + 1)]
  7.     
  8.     
  9.     for i, item in enumerate(items, start=1):
  10.         for j in xrange(1, weight + 1):
  11.             if item.weight <= j:
  12.                 if item.value + mem[i][j - item.weight] >= mem[i - 1][j]:
  13.                     mem[i][j] = item.value + mem[i][j - item.weight]
  14.                     grab[i][j] = 1
  15.                 else:
  16.                     mem[i][j] = mem[i - 1][j]
  17.             else:
  18.                 mem[i][j] = mem[i - 1][j]
  19.                 
  20.     itemList = []
  21.     n = len(items)
  22.     while n > 0 and weight >= 0:
  23.         if grab[n][weight]:
  24.             itemList.append(items[n-1])
  25.             weight -= items[n-1].weight
  26.         n -= 1
  27.     return itemList
  28.                 
  29. print ks(items, 15)

Existen soluciones triviales por ejemplo si no tengo ningún item a tomar entonces la mejor suma es 0 o si la capacidad de mi mochila es 0 entonces la mejor suma también es 0.

En la linea 1: Definimos la función que regresa una lista de items tal que sus valores sumados sea máximo y sus pesos sumados no rebasen la capacidad de la mochila. Y toma como parámetros una lista de items y la capacidad de la mochila.

Linea 2 a la 6: Creamos 2 matrices una para guardar las mejores sumas y otra para guardad que elementos hemos tomado.

Linea 9 a 18: Es donde ocurre la magia, iteramos sobre todos los items y pesos mayores i iguales a 1. Y por cada iteracion vamos resolviendo un mini-problema de la mochila que nos ayudara a resolver un problema de la mochila mas grande. Recuerda que las filas indican el ítem y que las columnas indican la capacidad de la mochila. Por lo que la fila (0, i) y (i, 0) están inicialmente en 0 por que o no tenemos items o no tenemos capacidad en la mochila.

Así que la lógica sigue siendo mas o menos la misma.

Linea 11, 17, 18: Preguntamos si podemos meter ese ítem a la mochila, si no podemos meter ese item a la mochila entonces la mejor solución es no tomar el ítem y por lo tanto agarramos lo mejor que podemos hacer con ese espacio no tomando ese item.

Linea 11: En adelante si podemos tomar el ítem entonces tenemos 2 caminos, tomar o no tomar el ítem. En este caso ambos caminos ya los hemos recorrido así que solo tenemos que checar sí el valor del ítem mas la mejor decisión con el peso restante es mayor o igual al valor de no tomar el ítem. Si es así entonces ponemos marcamos en la matriz que hemos tomado ese elemento y ponemos como solución el valor del ítem mas la mejor decisión con la capacidad restante de lo contrario ponemos como solución el caso donde hemos tomado el ítem.

Linea 20 a 27: Tenemos la parte donde obtenemos los items que formar la mejor combinación. Empezamos desde el ultimo ítem hasta el primer ítem y verificamos si esta marcado en la matriz de agarrados ademas la capacidad de la mochila va disminuyendo conforme tomemos un ítem.
Última edición por razpeitia; 10/12/2011 a las 18:27
  #2 (permalink)  
Antiguo 10/12/2011, 13:08
Avatar de razpeitia
Moderador
  
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 19 años, 1 mes
Puntos: 1360
Respuesta: [Aporte] Problema de la mochila
Código completo

Código Python: 
Ver original
  1. #coding: utf-8
  2.  
  3. class Item:
  4.     def __init__(self, value, weight):
  5.         self.value = value
  6.         self.weight = weight
  7.  
  8.     def __str__(self):
  9.         return "Value: %d - Weight: %d" % (self.value, self.weight)
  10.     
  11.     def __repr__(self):
  12.         return self.__str__()
  13.  
  14. items = [Item(4, 12),
  15.          Item(2, 2),
  16.          Item(2, 1),
  17.          Item(1, 1),
  18.          Item(10, 4),
  19.         ]
  20. c = 0
  21. def ks(index, weight):
  22.     global items
  23.     global c
  24.     c += 1
  25.  
  26.     if index >= len(items):
  27.         return 0
  28.  
  29.     item = items[index]
  30.  
  31.     if item.weight > weight:
  32.         return ks(index + 1, weight)
  33.     else:
  34.         return max(ks(index + 1, weight),
  35.                    ks(index + 1, weight - item.weight) + item.value)
  36.  
  37. print "Max sum: %d" % (ks(0, 20),)
  38. print "Iterations %d" % (c,)
  39. print
  40.  
  41. c = 0
  42. mem = {}
  43. def ks(index, weight):
  44.     global items
  45.     global c
  46.     global mem
  47.     c += 1
  48.  
  49.     case = (index, weight)
  50.     if case in mem:
  51.         return mem[case]
  52.  
  53.  
  54.     if index >= len(items):
  55.         mem[case] = 0
  56.         return mem[case]
  57.  
  58.     item = items[index]
  59.     grab_case = (index + 1, weight - item.weight)
  60.     no_grab_case = (index + 1, weight)
  61.  
  62.     if item.weight > weight:
  63.         mem[case] = ks(*no_grab_case)
  64.         return mem[case]
  65.     else:
  66.         if no_grab_case not in mem:
  67.             mem[no_grab_case] = ks(index + 1, weight)
  68.         if grab_case not in mem:
  69.             mem[grab_case] = ks(index + 1, weight - item.weight) + item.value
  70.         mem[case] = max(mem[grab_case], mem[no_grab_case])
  71.         return mem[case]
  72.  
  73. print "Max sum: %d" % (ks(0, 20),)
  74. print "Iterations %d" % (c,)
  75. print
  76.  
  77. def ks(items, weight):
  78.     mem = [[0 for j in xrange(weight + 1)]
  79.            for i in xrange(len(items) + 1)]
  80.     
  81.     grab = [[0 for j in xrange(weight + 1)]
  82.            for i in xrange(len(items) + 1)]
  83.     
  84.     
  85.     for i, item in enumerate(items, start=1):
  86.         for j in xrange(1, weight + 1):
  87.             if item.weight <= j:
  88.                 if item.value + mem[i][j - item.weight] >= mem[i - 1][j]:
  89.                     mem[i][j] = item.value + mem[i][j - item.weight]
  90.                     grab[i][j] = 1
  91.                 else:
  92.                     mem[i][j] = mem[i - 1][j]
  93.             else:
  94.                 mem[i][j] = mem[i - 1][j]
  95.                 
  96.     itemList = []
  97.     n = len(items)
  98.     while n > 0 and weight >= 0:
  99.         if grab[n][weight]:
  100.             itemList.append(items[n-1])
  101.             weight -= items[n-1].weight
  102.         n -= 1
  103.     return itemList
  104.                 
  105. print ks(items, 15)
  #3 (permalink)  
Antiguo 11/12/2011, 22:37
 
Fecha de Ingreso: febrero-2011
Mensajes: 32
Antigüedad: 13 años, 1 mes
Puntos: 0
Respuesta: [Aporte] Problema de la mochila
Impresionante aporte razpeitia.
Ví el problema de la mochila en estructuras de datos.
Lo voy a leer apenas tenga tiempo.
Saludos!.
  #4 (permalink)  
Antiguo 15/12/2011, 07:41
zz_sioux
Invitado
  
Mensajes: n/a
Puntos:
Respuesta: [Aporte] Problema de la mochila
mediante fuerza bruta, iteratividad y recursividad, directo a mi wiki de algoritmos.
Python no solo es un excelente lenguaje de programación, sino la mejor manera de expresar algoritmos, el pseudocódigo por excelencia, excelente aporte

Etiquetas: programa, formulario
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta

SíEste tema le ha gustado a 4 personas


« Tema Anterior | Próximo Tema »


La zona horaria es GMT -6. Ahora son las 17:03.