0votos

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

por josejuan hace 6 años

La más elegante en Haskell (para mi gusto, porque en la misma función queda cerrada [inmutable] frente a la memoización).

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
import Data.Function.Memoize 
 
gananciaMax precio = maxG (0, length precio - 1) 
  where maxG = memoize maxG' 
        maxG' (a, b) = if a == b 
                       then (precio!!a, precio!!a) 
                       else 
                         if g1 >= g2 
                         then (g1, precio!!b + t1) 
                         else (g2, precio!!a + t2) 
                       where (h1, t1) = maxG (a, b - 1) 
                             (h2, t2) = maxG (a + 1, b) 
                             g1 = precio!!b + h1 + t1 
                             g2 = precio!!a + h2 + t2 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.