Menu Close

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)

Pensamiento

Demos tiempo al tiempo:
para que el vaso rebose
hay que llenarlo primero.

Antonio Machado

Avanzado

7 soluciones de “Cambio con el menor número de monedas

  1. frahidzam
    monedas :: [Int] -> Int -> Maybe Int
    monedas xs n  | a /= []   = Just (minimum (map length a))
                  |otherwise = Nothing
      where a = sumas xs n
     
    sumas :: [Int] -> Int -> [[Int]]
    sumas [] 0 = [[]]
    sumas [] _ = []
    sumas (x:xs) n
      | x <= n    = map (x:) (sumas (x:xs) (n-x)) ++ sumas xs n
      | otherwise = sumas xs n
  2. javmarcha1
    import Data.List
     
    monedas :: [Integer] -> Integer -> Maybe Integer
    monedas xs x
      | z > 9^100 = Nothing
      | otherwise = Just (fromIntegral z)
       where z = minimum (longitudesN xs x)
     
     
    longitudesN :: [Integer] -> Integer -> [Integer]
    longitudesN xs x = [longitudes x xs n | n <- [0..(div x (maximum xs))]]
     
    longitudes :: Integer -> [Integer] -> Integer -> Integer
    longitudes 0 [] n = 0
    longitudes x [] n | x > 0 = 9^100
    longitudes x xs n | maximum xs > x = longitudes x (init xs) n
                      | rem x (maximum xs) == 0 = div x (maximum xs)
                      | otherwise = (div x (maximum xs))-n + longitudes
                      ((rem x (maximum xs))+(n*(maximum xs))) (init xs) 0
  3. luipromor
    monedas :: [Int] -> Int -> Maybe Int
    monedas xs n | esCombinacion n xs = Just (v ! n)
                 | otherwise = Nothing
                   where v = array (0,n) [ (i,f i) | i <- [0..n]]
                         esCombinacion 0 _ = True
                         esCombinacion _ []= False
                         esCombinacion a [b] = mod a b == 0
                         esCombinacion a xs | a < minimum xs = False
                                            | otherwise = or[  esCombinacion (mod a x) (filter (/=x) xs) | x <- xs]
                         f 0 = 0                  
                         f i |  n /= 0 = m + v ! n
                             | otherwise = m
                           where (m,n) = quotRem i (g [ x  | x <- xs , x<= i ]    )
                                 g (y:ys) = aux ys  (y ,div i y,v ! (mod i y))
                                   where aux [] (a,_,_) = a
                                         aux (x:xs) (a,b,c) | b + c > t  + o  = aux xs (x,t,o)
                                                            |otherwise = aux xs (a,b,c)
                                                             where t = div i x
                                                                   o = v ! (mod i x)
  4. luipromor
    monedas :: [Int] -> Int -> Maybe Int
    monedas xs n | esCombinacion1 n xs = Just (v ! n)
                 | otherwise = Nothing
                   where v = array (0,n) [ (i,f i) | i <- [0..n]]
                         esCombinacion1 0 _ = True
                         esCombinacion1 _ []= False
                         esCombinacion1 a [b] = mod a b == 0
                         esCombinacion1 a xs | a < minimum xs = False
                                             | otherwise = or[  esCombinacion1 (a-x)  (filter (<= (a-x)) xs) | x <- xs ]
                         f 0 = 0                  
                         f i | not (esCombinacion1 i xs) = i
                             | otherwise =  1 +  v ! (i-m)
                           where m = g [ x  | x <- xs , x<= i ]  
                                 g (y:ys) = aux ys  (y ,div i y,v ! (mod i y))
                                   where aux [] (a,_,_) = a
                                         aux (x:xs) (a,b,c) | b + c > t  + o && esCombinacion1 o xs = aux xs (x,t,o)
                                                            |otherwise = aux xs (a,b,c)
                                                             where t = div i x
                                                                   o = v ! (mod i x)
  5. ireprirod
    data Arbol a = N a [Arbol a]
                 deriving Show
     
    monedas :: [Int] -> Int -> Maybe Int
    monedas ms c = aux c ms 0
     where aux c ms i | null (n i)   = Nothing
                      | elem 0 (n i) = Just  i
                      | otherwise    = aux c ms (i+1)
     
                    where n i = nivel i (caminos c ms)
     
     
    caminos :: Int -> [Int] -> Arbol Int
    caminos c ms | c>m =  N c [caminos (c-m) ms | m<-ms, c-m>=0]
                 | otherwise = N c []
       where m = minimum ms
     
    nivel :: Int -> Arbol a -> [a]
    nivel 0 (N x _) = [x]
    nivel n (N _ xs) = concatMap (nivel (n-1)) xs
  6. ireprirod
    -- La definición anterior podría hacerse más eficiente modificando la función "caminos", ya que calculaba varias veces la misma combinación de monedas cambiando el orden.
     
    monedas1 :: [Int] -> Int -> Maybe Int
    monedas1 ms c = aux c ms 0
     where aux c ms i | null (n i)   = Nothing
                      | elem 0 (n i) = Just  i
                      | otherwise    = aux c ms (i+1) 
                    where n i = nivel i (cam c ms c)
     
    cam :: Int -> [Int] -> Int -> Arbol Int
    cam c xs n | c>=(head ds) = N c [cam (c-m) (dropWhile (<m) ds ) m | m<-ds,c>=m ]
               | otherwise   = N c [] 
      where ds = sort xs
     
    nivel :: Int -> Arbol a -> [a]
    nivel 0 (N x _) = [x]
    nivel n (N _ xs) = concatMap (nivel (n-1)) xs
     
    -- Comparación de eficiencia: 
    λ> monedas [1,2,5,10,20,50,100,200] 1003
    Just 7
    (2.91 secs, 524,677,880 bytes)
    λ> monedas1 [1,2,5,10,20,50,100,200] 1003
    Just 7
    (0.05 secs, 9,786,712 bytes)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.