Cambio con el menor número de monedas
El problema del cambio con el menor número de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas
1, 1, 1, 1, 1, 1 1, 1, 1, 3 1, 1, 4 3, 3
El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.
Definir
monedas :: [Int] -> Int -> Maybe Int
tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,
monedas [1,3,4] 6 == Just 2 monedas [2,5,10] 3 == Nothing monedas [1,2,5,10,20,50,100,200] 520 == Just 4
Soluciones
import Data.Array ((!), array) -- 1ª solución -- =========== monedas :: [Int] -> Int -> Maybe Int monedas ms x | null cs = Nothing | otherwise = Just (minimum (map length cs)) where cs = cambios ms x -- (cambios ms x) es la lista de las foemas de obtener x sumando monedas -- de ms. Por ejemplo, -- λ> cambios [1,5,10] 12 -- [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]] -- λ> cambios [2,5,10] 3 -- [] -- λ> cambios [1,3,4] 6 -- [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]] cambios :: [Int] -> Int -> [[Int]] cambios _ 0 = [[]] cambios [] _ = [] cambios (k:ks) m | m < k = [] | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++ cambios ks m -- 2ª solución -- =========== monedas2 :: [Int] -> Int -> Maybe Int monedas2 ms n | sol == infinito = Nothing | otherwise = Just sol where sol = aux n aux 0 = 0 aux k = siguiente (minimo [aux (k - x) | x <- ms, k >= x]) infinito :: Int infinito = 10^30 minimo :: [Int] -> Int minimo [] = infinito minimo xs = minimum xs siguiente :: Int -> Int siguiente x | x == infinito = infinito | otherwise = 1 + x -- 3ª solución -- =========== monedas3 :: [Int] -> Int -> Maybe Int monedas3 ms n | sol == infinito = Nothing | otherwise = Just sol where sol = v ! n v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x]) -- Comparación de eficiencia -- ========================= -- λ> monedas [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (0.02 secs, 871,144 bytes) -- λ> monedas2 [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (15.44 secs, 1,866,519,080 bytes) -- λ> monedas3 [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (0.01 secs, 157,232 bytes) -- -- λ> monedas [1,2,5,10,20,50,100,200] 188 -- Just 7 -- (14.20 secs, 1,845,293,080 bytes) -- λ> monedas3 [1,2,5,10,20,50,100,200] 188 -- Just 7 -- (0.01 secs, 623,376 bytes)