Cambio con el menor número de monedas

PorJosé A. Alonso 15-marzo-201926-marzo-2022

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

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

1	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

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)

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

7 Comentarios

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

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

Responder

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

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

Responder

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)

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)

Responder

luipromor dice:

16-marzo-2019 a las 15:08

Definición incorrecta

Responder

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)

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)

Responder

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

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

Responder

-- 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)

-- 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)

Responder

Cambio con el menor número de monedas

Soluciones

Pensamiento

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico