Problema de las vacas con programación dinámica
De Wikipedia, la enciclopedia libre
Este artículo debería estar en Wikilibros ya que es una guía o manual en vez de un verdadero artículo enciclopédico.
Si modificas este artículo dándole una orientación enciclopédica, elimina por favor esta plantilla.
Hay 2 vacas que se alimentan de pienso y para alimentarlas se llena una hilera de cubos (nº par). Cada uno de ellos tiene una cantidad pi indicada en el cubo (todas las cantidades son distintas).Cada vaca en su turno elige un extremo, hasta que se agotan los cubos, siendo el objetivo de ambas comer lo más posible. La estrategia de la vaca 1 consiste en pensar poco y coger el cubo de los extremos que esté más lleno. La vaca 2 prefiere pensar 1 poco más.
Tabla de contenidos |
[editar] Ejemplo
Demostramos que la estrategia de la vaca 1 no es óptima dando un contraejemplo:
La vaca 1 cogería primero el de 20 por lo tanto quedarían los siguientes:
Como la vaca 2 elige de forma inteligente cogería el 50 quedando:
La vaca 1 ahora elegiría el 15 y la vaca 2 el 10.
Por tanto los cubos que han cogido cada una son
Vaca1 -------- 20,15 -------- Total = 35 Vaca2 -------- 50,10 -------- Total = 60
Como vemos, la vaca 2 come más, por lo tanto vemos que la estrategia de la vaca 1 no es la apropiada.
[editar] Función
Vamos a definir la estrategia de la vaca 2:
La función que vamos a utilizar va a ser la siguiente:
max_comida (i, j)= máxima cantidad de comida que puede comer la vaca 2 cuando empieza a
comer con cubos entre i…j
Por tanto recursivamente va a ser del tipo:
Esto tiene sentido para n>=4 ya que si solo hay 2 cubos se coge el más grande.
[editar] Caso base
Si nº cubos = 2 entonces
max_comida(i, i+1)=max{pi , pi+1}
En el algoritmo vamos a construir una tabla donde vamos a ir guardando los valores según la función recursiva. La tabla la vamos a recorrer en diagonal, pero solo vamos a recorrer aquellas que tengan cubos pares, ya que las diagonales de cubos impares son las comidas por la vaca 1 y x l tanto nuestro algoritmo ya lo va a hacer en la misma vuelta que la vaca 2(Es decir cada 2 diagonales) La diagonal inferior no tiene sentido utilizarla y será toda 0.
Estas son las diagonales que vamos a recorrer (es un ejemplo con 6 cubos).
[editar] Algoritmo
Function vacas(P[1..n]:int) dev maximo
var come_i, come_j: int
var max_comida[1..n,1..n]:int
para i = 1 hasta n-1 hacer
max_comida[i, i+1]= max (P[i], P[i+1])
fpara
para d=3 hasta d=n-1 paso 2 hacer
para i=1 hasta n-d hacer
j=i+d
si (P[j]> P[i+1]) entonces come_i = max_comida[i+1,j-1]
sino come_i = max_comida[i+2,j]
fsi
si (P[i]< P[j-1]) entonces come_j = max_comida[i, j-2]
sino come_j = max_comida[i+1,j-1]
fsi
max_comida[i, j] = max (P[i] +come_i, P[j] + come_j)
fpara
fpara
maximo= max_comida[1,n]
ffun
[editar] Fuentes
Martí Oliet, N.; Ortega Mallén, Y.; Verdejo López, J. A.; Estructuras de datos y
métodos algorítmicos:
Ejercicios resueltos; Colección Prentice Practica, Pearson/Prentice Hall, 2003;
