1votos

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

por josejuan hace 6 años

Este tipo de problemas normalmente se resuelven bien por inducción, es decir, buscando una recurrencia que permita trabajar sobre datos "internos" a los ya procesados. En cualquier lenguaje que permita definir una función memoizada la implementación es inmediata.

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
''' 
  Por sencillez no usaré índices y supondré sólo un tubo de 3 elementos A, B y C. 
 
  Entonces tenemos que la ganancia si se venden en el orden A, B y C a partir del día 'n' es: 
 
    g(n) = A n + B (n + 1) + C (n + 2) = n (A + B + C) + B + 2 C 
 
  si lo retrasamos un día más, tenemos que la ganancia es 
 
   g(n+1) = A (n + 1) + B (n + 2) + C (n + 3) = n (A + B + C) + A + 2 B + 3 C 
 
  es decir, dado un tubo de chocolates vendido en un orden determinado, cada día que 
  retrasamos la venta, el precio se incrementa en 
 
   g(n + 1) - g(n) = A + B + C 
 
  Por tanto, para poder combinar un cómputo interno (en la inducción) con uno actual, sólo 
  nos hace falta almacenar: 
 
    (la ganancia, la suma de los precios iniciales) 
 
  Es decir, supongamos que tenemos 'p' chocolates cuya mejor ganancia es G y cuya suma total 
  de los precios es T, entonces, si en lugar de 'p' chocolates tenemos 'p + 1', la ganancia si 
  vendemos éste primero es 
 
     precio_nuevo_chocolate + G + T 
 
  supuesto que vendemos este chocolate antes que todos los otros 'p'. 
   
  Y ahí está entonces la división del problema que es memoizada (porque muchas divisiones 
  del chocolate aparecerán recurrentemente). 
 
  Bueno, se que no me he explicado muy bien pero espero que se entienda XD XD XD 
''' 
 
precio = [3, 1, 1, 1, 1, 2, 2, 2, 2] 
 
@memoized 
def MaxGanancia(a, b): 
  if a == b: 
    return (precio[a], precio[a]) 
  else: 
    (g1, t1) = MaxGanancia(a, b - 1) 
    (g2, t2) = MaxGanancia(a + 1, b) 
 
    G1 = precio[b] + g1 + t1 
    G2 = precio[a] + g2 + t2 
 
    if G1 >= G2: 
      return (G1, precio[b] + t1) 
    else: 
      return (G2, precio[a] + t2) 
 
print(MaxGanancia(0, len(precio) - 1)) # da 77 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.