0votos

Programación dinámica problema de tubo de chocolates en Haskell

por josejuan hace 6 años

Se que se pide resolver mediante programación dinámica, pero siempre me resulta divertido ver si los desafíos pueden ser resueltos fácilmente usando programación lineal (mediante LP se puede representar cualquier circuito lógico).

Utiliza programación dinámica para resolver el problema de ganancia referente al tubo de chocolates

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
-- Usando GLPK, http://www.gnu.org/software/glpk/  
import Data.List  
import Control.Monad  
import Data.LinearProgram  
import Data.LinearProgram.GLPK  
import qualified Data.Map as M  
 
{-- 
 
  Se que se pide resolver mediante programación dinámica, pero 
  siempre me resulta divertido ver si los desafíos pueden ser 
  resueltos fácilmente usando programación lineal (mediante LP 
  se puede representar cualquier circuito lógico). 
 
  En este caso, tenemos una serie de chocolates cuyos precios 
  podemos enumerar como: 
 
        P1   P2   ...   Pn-1   Pn        --> eje 'i' 
 
  Podemos definir una matriz (eje 'j') que indique que día (j) 
  se vende una chocolatina (i). 
 
 
        P1   P2   ...   Pn-1   Pn        --> eje 'i' 
        0    0    ...   0      1 
        0    0    ...   1      0 
        1    0    ...   0      0 
        ........................ 
        0    0    .1.   0      0 
 
        eje 'j' 
 
  A los coeficientes de la matriz los llamaremos Aij. 
 
  Entonces, es obvio que la suma de columnas debe dar siempre 1 y 
  que la suma de filas debe dar siempre 1, por tanto, tenemos las 
  ecuaciones 
 
 
       Suma i=1..n de Aij = 1 para todo j=1..n 
       Suma j=1..n de Aij = 1 para todo i=1..n 
 
  Para que un chocolate pueda venderse, debe haberse vendido el de 
  su izquierda o bien el de la derecha, excepto el primero y últimos 
  que siempre se pueden vender, por lo que para cada chocolate 'i', 
  tenemos otras dos ecuaciones 
 
       Aij <= Suma h=1..j de A(i-1)h + A(i+1)h para todo i=2..n-1, j=1..n 
 
  Por último, sólo queda representar la función de optimización, que 
  en este caso se trata de maximizar la expresión 
 
      Suma i=1..n, j=1..n de Pi * j * Aij 
 
  Cada chocolate 'i' se vende el día 'j' en que Aij = 1. 
 
  Obviamente, todas las variables Aij son binarias. 
 
--}  
 
-- Las incógnitas de la matriz Aij 
a :: Int -> Int -> (Int, Int) 
a i j = (i, j) 
  
--  
bestBuyProblem :: [Int] -> LP (Int, Int) Int 
bestBuyProblem ps = execLPM $ do setDirection Max 
                                 -- Restricciones en el mismo orden que en la explicación 
                                 mapM_ (\j -> equalTo (varSum [a i j | i <- ns]) 1) ns 
                                 mapM_ (\i -> equalTo (varSum [a i j | j <- ns]) 1) ns 
                                 mapM_ (\(i, j) -> geqTo (leftRightCols i j ^-^ (var $ a i j)) 0) [(i, j) | i <- [2..n-1], j <- ns] 
                                 setObjective $ linCombination $ matrix (\i j -> (price i j, a i j)) 
                                 mapM_ (\v -> setVarKind v BinVar) $ matrix a 
 
  where n = length ps 
        ns = [1..n] 
        matrix f = [f i j | i <- ns, j <- ns] 
        price i j = ps!!(i - 1) * j 
        leftRightCols i j = varSum $ concat [[a (i - 1) h, a (i + 1) h] | h <- [1..j]] 
                    
-- Wrapper suponiendo que siempre hay solución (aquí siempre)  
bestBuySolver :: [Int] -> IO [(Int, Int)] 
bestBuySolver ps = do  
  (_, Just (_, m)) <- glpSolveVars (mipDefaults { msgLev = MsgErr }) $ bestBuyProblem ps  
  return $ map fst. M.toList. M.filter (==1) $ m  
 
-- Leer entrada, resolver y formatear: 
main = do 
  getLine -- ignorar nº de 
  precios <- getLine >>= return . map read . words 
 
  bestBuySolver precios >>= mapM_ format . sortBy ((.snd).compare.snd) 
 
  where format (i, j) = putStrLn $ "El día " ++ show j ++ " se vende la chocolatina " ++ show i 
 
{-- 
 
  Ejemplo de uso: 
 
  solveet$ echo -e "5\n2 1 5 4 3" | runghc ./chocolates.hs 
  El día 1 se vende la chocolatina 1 
  El día 2 se vende la chocolatina 2 
  El día 3 se vende la chocolatina 5 
  El día 4 se vende la chocolatina 4 
  El día 5 se vende la chocolatina 3 
  solveet$ _ 
 
--} 
2 comentarios
0votos

Escrito por padidica hace 4 años

puedes resolverlo en java???
0votos

Escrito por josejuan hace 4 años

Hola @padidica,

si lo que buscas es una solución al desafío en Java, sugiero que tomes cualquiera de las que usan memoización, en mi solución Python explico detalladamente la estrategia de resolución y creo que (salvo memoización que puedes hacerlo con un simple diccionario) te resultará inmediato trasladarlo a Java.

Si lo que buscas es ésta solución (usando programación lineal entera) en Java, no creo que merezca la pena, porque el lenguaje (en este caso Haskell) únicamente se usa para montar el sistema de ecuaciones.

¡Un saludo!

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.