-- I1M 2021-22: Relación 26
-- El problema de la mochila
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================
-- ============================================================================
-- Librerías auxiliares
-- ============================================================================
import qualified Data.Array as A
import qualified Data.Matrix as M
import qualified Data.Vector as V
type Matriz a = A.Array (Int,Int) a
type Vector a = A.Array Int a
-- ============================================================================
--
-- ENUNCIADO:
--
-- Suponga n objetos, numerados desde el 0 hasta el n-1.
--
-- Cada objeto tiene un valor determinado dado por un vector "valor", de tal
-- forma que el elemento i-ésimo de este vector nos proporciona el valor del
-- objeto i-ésimo.
--
-- Cada objeto tiene un peso determinado dado por un vector "peso", de tal forma
-- que el elemento i-ésimo del vector nos proporciona el peso del objeto
-- i-ésimo.
--
-- Suponga además que tenemos una mochila que soporta un peso máximo "w".
-- El problema de la mochila consiste en determinar qué objetos deben entrar en
-- la mochila para maximizar el valor de la misma teniendo en cuenta la
-- capacidad máxima.
--
-- En este problema los objetos no se pueden partir, es decir, que un objeto
-- determinado, o entra entero en la mochila (con todo su valor y todo su peso),
-- o no entra nada de él. Además, sólo existe una instancia de cada uno de los
-- objetos, es decir, no se pueden repetir.
--
-- Por ejemplo, dado este problema:
n :: Int
w :: Int
peso :: Vector Int
valor :: Vector Int
n = 4
w = 8
peso = A.listArray (0,n-1) [4, 3, 5, 2]
valor = A.listArray (0,n-1) [10, 40, 30, 20]
-- Una solución válida sería meter los objetos 2 y 3, que suman un peso total
-- de 7 (entrarían en la mochila) y suman un valor total de 50. Una solución
-- mejor sería meter los objetos 1 y 3, que pesan 5 y valen 60. El objetivo final
-- es buscar la solución óptima.
--
-- Para ello se va a hacer uso de la técnica de Programación Dinámica usando
-- como estructura auxiliar una matriz M con índices por filas que van desde 0
-- hasta n-1, y con índices por columnas que van desde 0 hasta la capacidad
-- de la mochila "w".
--
-- En el ejemplo anterior la matriz quedaría dimensionada así:
--
-- 0 1 2 3 4 5 6 7 8
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 0 | | | | | | | | | |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 1 | | | | | | | | | |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 2 | | | | | | | | | |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 3 | | | | | | | | | |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
--
-- La definición de cada posición de la matriz sería la siguiente:
-- M(i,j) es el máximo valor de una mochila de capacidad máxima "j" cuando puedo
-- elegir meter hata el objeto i-ésimo.
--
-- Así:
-- * En la fila 0 sólo puedo usar el objeto 0.
-- * En la fila 1 sólo se pueden usar los objetos 0 y 1.
-- * En la fila n-1 podría usar todos los objetos.
-- * En la columna 0, la capacidad de la mochila es 0, por lo que sólo podrían entrar
-- objetos de peso 0.
-- * En la columna 1, la capacidad de la mochila es 1.
-- * En la columna w estaría la mochila del enunciado.
--
-- Por lo tanto, la solución final estaría en el elemento M(n-1,w), en la
-- esquina inferior derecha.
--
-- Así, si empezamos a recorrer la matriz por la fila 0 tenemos sólo dos
-- posiblidades, que no quepa el objeto (por que su peso supere la capacidad)
-- o que quepa el objeto al completo (con lo que ya tendríamos su valor):
--
-- 0 1 2 3 4 5 6 7 8
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 1 | | | | | | | | | |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 2 | | | | | | | | | |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 3 | | | | | | | | | |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
--
-- A partir de la fila 1 (genéricamente la "i") habrá las mismas posibilidades,
-- que quepa el objeto o que no:
-- * Si el objeto "i" no cabe, habrá que descartarlo y pasar a preguntar por los
-- "i-1" anteriores.
-- * Si el objeto "i" cabe, habrá que preguntarse por la mejor de dos opciones.
-- - No meter el objeto aunque quepa.
-- - Meter el objeto, con lo que tendríamos su valor pero decrementammos la
-- capacidad restante de la mochila.
--
-- De esta forma, la matriz auxiliar acabaría así:
--
-- 0 1 2 3 4 5 6 7 8
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 1 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 50 | 50 |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 2 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 50 | 70 |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
-- 3 | 0 | 0 | 20 | 40 | 40 | 60 | 60 | 60 | 70 |
-- * --- * --- * --- * --- * --- * --- * --- * --- * --- *
--
-- Pasos para resolver el problema:
-- 1. Plantee una ecuación en recurrencia que permita resolver este problema.
-- 1.1. Preste atención a los casos base.
-- 1.2. Resuelva el caso recursivo atendiendo a la definición y a los casos
-- particulares que hay en el ejemplo
-- 2. Implemente la función Haskell que construya la matriz anterior y devuelva
-- el elemento en la posición inferior derecha. Para ello use la signatura:
-- mochila :: Vector Int -> Vector Int -> Int -> Int -> Int
-- Como ejemplo de la llamada anterior podríamos hacer:
-- mochila peso valor w n == 70
-- 3. Cree una versión nueva de la función anterior que devuelva una lista con
-- los índices de los objetos que, al meterlos en la mochila, maximizan el
-- valor de la misma.
--
-- ============================================================================
mochila :: Vector Int -> Vector Int -> Int -> Int -> Int
mochila peso valor w n = m A.! (n-1,w)
where m = A.listArray ((0,0),(n-1,w)) [ponElem i j | i <- [0..n-1],
j <- [0..w]]
ponElem i j | i == 0 && j < peso A.! i = 0
| i == 0 && j >= peso A.! i = valor A.! i
| i > 0 && j < peso A.! i = m A.! (i-1,j)
| otherwise = max (m A.! (i-1,j)) (m A.! (i-1,j - peso A.! i) + valor A.! i)
mochilaObjetos :: Vector Int -> Vector Int -> Int -> Int -> [Int]
mochilaObjetos peso valor w n = calculaObjetos m (n-1) w
where m = A.listArray ((0,0),(n-1,w)) [ponElem i j | i <- [0..n-1],
j <- [0..w]]
ponElem i j | i == 0 && j < peso A.! i = 0
| i == 0 && j >= peso A.! i = valor A.! i
| i > 0 && j < peso A.! i = m A.! (i-1,j)
| otherwise = max (m A.! (i-1,j)) (m A.! (i-1,j - peso A.! i) + valor A.! i)
calculaObjetos m i j | i > 0 && m A.! (i,j) == m A.! (i-1,j) = calculaObjetos m (i-1) j
| i > 0 && m A.! (i,j) /= m A.! (i-1,j) = i:(calculaObjetos m (i-1) (j - peso A.! i))
| i == 0 && m A.! (i,j) /= 0 = [0]
| otherwise = []
-- ============================================================================
data Mat = Mat [[String]] Int
instance Show Mat where
show (Mat x m) | length x == 1 = "( " ++ showRow (x !! 0) m ++ ")"
| otherwise = "/ " ++ (showRow (x !! 0) m) ++ "\\\n" ++
(showIntermediateRows x 1 m) ++
"\\ " ++ (showRow (x !! (length x - 1)) m) ++ "/"
showRow :: [String] -> Int -> String
showRow [] m = []
showRow (x:xs) m = (replicate (m - (length x)) ' ') ++ x ++ " " ++ (showRow xs m)
showIntermediateRows :: [[String]] -> Int -> Int -> String
showIntermediateRows xxs i m | i >= length xxs - 1 = []
| otherwise = "| " ++ showRow (xxs !! i) m ++ "|\n" ++
showIntermediateRows xxs (i+1) m
printMatrix :: Show a => M.Matrix a -> Mat
printMatrix m = Mat (M.toLists nm) mx
where nm = (M.mapPos (\ (i,j) e -> show e) m)
mx = maximum (map (length) (M.toList nm))
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)