El problema de la mochila (mediante espacio de estados)
Se tiene una mochila de capacidad de peso p y una lista de n para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en la mochila sin sobrepasar la capacidad de la mochila colocando el máximo valor posible.
Para solucionar el problema se definen los siguientes tipos:
- Una solución del problema de la mochila es una lista de objetos.
|
1 |
type SolMoch = [Objeto] |
- Los objetos son pares formado por un peso y un valor
|
1 |
type Objeto = (Peso,Valor) |
- Los pesos son número enteros
|
1 |
type Peso = Int |
- Los valores son números reales.
|
1 |
type Valor = Float |
- Los estados del problema de la mochila son 5-tupla de la (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el peso de los objetos colocados, l es el límite de la capacidad de la mochila, o es la lista de los objetos colocados (ordenados de forma creciente según sus pesos) y s es la solución parcial.
|
1 |
type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch) |
Usando el procedimiento de búsqueda en profundidad, definir la función
|
1 |
mochila :: [Objeto] -> Peso -> (SolMoch,Valor) |
tal que mochila os l es la solución del problema de la mochila para la lista de objetos os y el límite de capacidad l. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
> mochila [(2,3),(3,5),(4,6),(5,10)] 8 ([(5,10.0),(3,5.0)],15.0) > mochila [(2,3),(3,5),(5,6)] 10 ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) > mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35 ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0) > mochila [(2,2.8),(3,4.4),(5,6.1)] 10 ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
module BEE_Mochila where import BusquedaEnProfundidad (buscaProfundidad) import Data.List (sort) import Test.Hspec (Spec, hspec, it, shouldBe) type Peso = Int type Valor = Float type Objeto = (Peso,Valor) type SolMoch = [Objeto] type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch) mochila :: [Objeto] -> Peso -> (SolMoch,Valor) mochila os l = (sol,v) where (v,_,_,_,sol) = maximum (buscaProfundidad sucesoresMoch esObjetivoMoch (inicial os l)) -- (inicial os l) es el estado inicial del problema de la mochila -- para la lista de objetos os y el límite de capacidad l inicial :: [Objeto] -> Peso -> NodoMoch inicial os l = (0,0,l,sort os,[]) -- (sucesoresMoch e) es la lista de los sucesores del estado e en el -- problema de la mochila para la lista de objetos os y el límite de -- capacidad l. sucesoresMoch :: NodoMoch -> [NodoMoch] sucesoresMoch (v,p,l,os,solp) = [( v+v', p+p', l, [o | o@(p'',_) <- os, p''>=p'], (p',v'):solp ) | (p',v') <- os, p+p' <= l] -- (esObjetivoMoch e) se verifica si e es un estado final el problema de -- la mochila para la lista de objetos os y el límite de capacidad l . esObjetivoMoch :: NodoMoch -> Bool esObjetivoMoch (_,p,l,(p',_):_,_) = p+p'>l -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ mochila [(2,3),(3,5),(4,6),(5,10)] 8 `shouldBe` ([(5,10.0),(3,5.0)],15.0) it "e2" $ mochila [(2,3),(3,5),(5,6)] 10 `shouldBe` ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) it "e3" $ mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35 `shouldBe` ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0) it "e4" $ mochila [(2,2.8),(3,4.4),(5,6.1)] 10 `shouldBe` ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4) -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0424 seconds -- 4 examples, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
from src.BusquedaEnProfundidad import buscaProfundidad Peso = int Valor = float Objeto = tuple[Peso, Valor] SolMoch = list[Objeto] NodoMoch = tuple[Valor, Peso, Peso, list[Objeto], SolMoch] # inicial(os, l) es el estado inicial del problema de la mochila # para la lista de objetos os y el límite de capacidad l def inicial(os: list[Objeto], l: Peso) -> NodoMoch: return (0,0,l,sorted(os),[]) # sucesoresMoch(e) es la lista de los sucesores del estado e en el # problema de la mochila para la lista de objetos os y el límite de # capacidad l. def sucesoresMoch(n: NodoMoch) -> list[NodoMoch]: (v,p,l,os,solp) = n return [( v+v1, p+p1, l, [(p2,v2) for (p2,v2) in os if p2 >= p1], [(p1,v1)] + solp ) for (p1,v1) in os if p + p1 <= l] # esObjetivoMoch(e) se verifica si e es un estado final el problema de # la mochila para la lista de objetos os y el límite de capacidad l . def esObjetivoMoch(e: NodoMoch) -> bool: (_, p, l, os, _) = e (p_, _) = os[0] return p + p_ > l def mochila(os: list[Objeto], l: Peso) -> tuple[SolMoch, Valor]: (v,_,_,_,sol) = max(buscaProfundidad(sucesoresMoch, esObjetivoMoch, inicial(os, l))) return (sol, v) # Verificación # ============ def test_Mochila() -> None: assert mochila([(2,3),(3,5),(4,6),(5,10)], 8) == \ ([(5,10.0),(3,5.0)],15.0) assert mochila([(2,3),(3,5),(5,6)], 10) == \ ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) assert mochila([(2,2.8),(3,4.4),(5,6.1)], 10) == \ ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4) print("Verificado") # La verificación es # >>> test_Mochila() # Verificado |