# TDA | Teoría: Programación dinamica
## Notas del cormen
Para desarrollar una solución con programación dinamica, hay que seguir una secuencia de 4 pasos
1. Caracterizar a la estructura con una solución optima.
2. Definir recursivamente el valor de una solución optima.
3. Computar el valor de una solución optima, tipicamente bottom-up.
4. Construir una solución optima "from computed information".
- Sí necesitas solo el valor de la solución optima, y no la solución en sí, entonces podés saltearte el paso 4.
- Cuando haces el paso 4, a veces se se paga por mantener informacion adicional durante el paso 3, entonces podés construir una solución optima.
### El problema de cortar varillas
- Serling Enterprise compra largas varillas de acero y las corta en varillas mas cortas que vende. Cada corte es gratuito.
- La administración quiere optimizar la mejor manera de cortar estas varillas sacando la mejor ganancia posible.
- Para $i = 1,2 ...,$ el precio $P_i$ en dolares americanos son lo que cobran por cada varilla de longitud i pulgadas.
- La longitud de cada varilla en pulgadas es siempre un numero entero $\mathbb{Z}$, detereminar la maxima ganancia de $r_n$ obtenible por cortar las varillas y venderla en pedazos. sí el precio de $p_n$ de una varilla de longitud $n$ es lo suficientemente largo, una solución optima podría ser no cortarla. O sea, no cortar la varilla puede ser una solución optima también.
- considerar el caso cuando $n=4$ cortar una varilla de 4 pulgadas en dos varillas de 2 pulgadas cada una, produce una ganancia de $p_2 + p_2 = 5 + 5 = 10$ lo cual es optimo. **~~Nota de Gaspar: No veo porque sería optimo ganancia 10~~**
- La empresa puede cortar una varilla de longitud $n$ en $2^{n-1}$ formas diferentes, desde que tienen una forma independiente de cortar ó no cortar.
- Para $i = 1,2, ...,n-1$ notamos una decomposición de piezas usando una notación aditiva, entonces para $7 =2+2+3$ se indica que la varilla de longitud 7 se corta en tres piezas: dos de longitud 2 y una de longitud 3.
- Sí una solución optima se corta la varilla en $k$ piezas, para $1\leq k\leq n$ entonces una descomposición optima sería: $n= i_1 + i_2 + ... + i_k$.
- En esta figura se ven las 8 posibles formas de cortar la varilla de tamaño la estrategia optima sería cortar la pieza en dos piezas de longitud 2 ( c ) que tiene un valor total de 10.
- $r_n = p_{i_1} + p_{i_2} + ... + p_{i_k}$
- para el ejemplo de la figura de arriba se puede determinar la ganancia optima $r_i$ para $i = 1,2,...,10$ por inspección con con la correspondiente descomposición optima:
- $r_1 = 1$ de la solución 1=1 (sin cortes)
- $r_2 = 5$ de la solución 2=2 (sin cortes)
- $r_3 = 8$ de la solución 3=3 (sin cortes)
- $r_4$
###### Lista incompleta, pagina 364 del cormen
- Una generalización es que podemos expresar a los valores $r_n$ para $n \geq 1$ en terminos de ganncia optima para varillas más cortas:
- $r_n =$ max{$p_n,r_1 + r_{n-1}, r_2 + r_{n-2}, ..., r_{n-1} + r_1$}
- $p_n$ corresponde a no hacer ningún corte y vender la varilla con el tamaño $n$ original.
- los otros $n-1$ argumentos del maximo corresponden a la maxima ganacia obtenida por hacer el corte inicial de la varilla en dos piezas, obteniendo ganancias $r_i$ y $r_{n-i}$.
- ...
- $r_n =$ max{$p_i + r_n-i : 1 \leq i \leq n$}
### Implementación recusriva top-down del problema de la varilla de metal
- Toma de input un arreglo `p[1:n]` de precios y un entero $n$ que retorna la maxima ganancia posible de una varilla de longitud $n$. para longitud $n = 0$, sin ganancia posible, y entonces `CUT-ROD` retorna 0 en linea 2. Linea 3 inicializa el max-rev (la ganancia maxima) $q$ to $-\infty$, entonces el **for** loop en lineas 4-5 computa correctamente:
- $q$ = max{$p_i + CUT-ROD(p,n-i)\ : \ 1 \leq i \leq n$}
- linea 6 retorna este valor, una simple inducción demuestra que la respuesta es igual a la respuesta deseada $r_n$.
\begin{align*}
\text{CUT-ROD}(p, n) & : \\
1.\ & \text{si } n == 0 \\
2.\ & \quad \text{retorna } 0 \\
3.\ & q = -\infty \\
4.\ & \text{para } i = 1 \text{ hasta } n \\
5.\ & \quad q = \max(q, p[i] + \text{CUT-ROD}(p, n - i)) \\
6.\ & \text{retorna } q
\end{align*}
En python una forma fuerte de hacerlo:
```python
import time
def cutRod(p,n):
if n == 0:
return 0
q = float('-inf')
for i in range(1,n+1):
q = max(q,p[i]+cutRod(p,n-i))
return q
```
- El problema de acá es que se llama tantas veces a sí mismo una y otra vez con los mismos valores de parametro que recalcula y resuelvo los mimos subproblemas repetidamente.
- No voy a transcribir toda la explicación del cormen pero basicamente es exponencial.
### Implementación del problema de la varilla con programción dinamica
- En vez de resolver los mismos subproblemas repetidamente, los subproblemas se resuelven una sola vez y se guardan.
- Vamos a ver la tecnica de memoización top-down que escriube el procedimiento recursivamente de una manera natural pero modificamos el resultado guardado por cada subproblema en un arreglo o diccionario.
- Luego también está la tecnica de bottom-up que tipicamente depende de alguna noción natural del tamaño del subproblema.
#### MEMOIZED-CUT-ROD
- Utiliza memorización para mejorar la eficiencia del cálculo recursivo, evitando recalculos de subproblemas ya resueltos
\begin{align*}
\text{MEMOIZED-CUT-ROD}(p, n): \\
1.\ & \text{let } r[0..n] \text{ be a new array} \\
2.\ & \text{for } i = 0 \text{ to } n \\
3.\ & \quad r[i] = -\infty \\
4.\ & \text{return MEMOIZED-CUT-ROD-AUX}(p, n, r)
\end{align*}
\begin{align*}
\text{MEMOIZED-CUT-ROD-AUX}(p, n, r): \\
1.\ & \text{if } r[n] \geq 0 \\
2.\ & \quad \text{return } r[n] \\
3.\ & \text{if } n == 0 \\
4.\ & \quad q = 0 \\
5.\ & \text{else} \\
6.\ & \quad q = -\infty \\
7.\ & \quad \text{for } i = 1 \text{ to } n \\
8.\ & \quad \quad q = \max(q, p[i] + \text{MEMOIZED-CUT-ROD-AUX}(p, n-i, r)) \\
9.\ & \quad r[n] = q \\
10.\ & \text{return } q
\end{align*}
### BOTTOM UP CUT ROD
\begin{align*}
\text{BOTTOM-UP-CUT-ROD}(p, n): \\
1.\ & \text{let } r[0..n] \text{ be a new array} \\
2.\ & r[0] = 0 \\
3.\ & \text{for } j = 1 \text{ to } n \\
4.\ & \quad q = -\infty \\
5.\ & \quad \text{for } i = 1 \text{ to } j \\
6.\ & \quad \quad q = \max(q, p[i] + r[j-i]) \\
7.\ & \quad r[j] = q \\
8.\ & \text{return } r[n]
\end{align*}
#### Codigo memoizado:
```python
def memoizedCutRod(p, n):
r = [float('-inf')]*(n+1) # Inicializa r con -infinito para todas las posiciones
r[0] = 0 # El valor máximo para una varilla de longitud 0 es 0
return memoizedCutRodAux(p, n, r)
def memoizedCutRodAux(p, n, r):
if r[n] >= 0: #Caso base: Si ya tenemos calculado el valor para longitud n, lo retornamos
return r[n]
if n == 0:
q = 0
else:
q = float('-inf')
for i in range(1, n+1): # Considera cada posible primer corte
q = max(q, p[i-1] + memoizedCutRodAux(p, n-i, r)) # Ajusta el índice para p
r[n] = q # Almacena el resultado calculado para n
return q
```
#
```bash
# Ejemplo de uso
p = [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] # Ejemplo de precios
n = 40 # Longitud de la varilla
The maximum obtainable price is: 40
The execution time was: 0.0004220008850097656 seconds
```
#### Arbol de recursión
- Para `n=4` y `p=[1,5,8,9]`
#
#### Codigo bottom-up:
\begin{align*}
\text{BOTTOM-UP-CUT-ROD}(p, n): \\
1.\ & \text{let } r[0..n] \text{ be a new array} \\
2.\ & r[0] = 0 \\
3.\ & \text{for } j = 1 \text{ to } n \\
4.\ & \quad q = -\infty \\
5.\ & \quad \text{for } i = 1 \text{ to } j \\
6.\ & \quad \quad q = \max(q, p[i] + r[j-i]) \\
7.\ & \quad r[j] = q \\
8.\ & \text{return } r[n]
\end{align*}
```python
def bottomUpCutRod(p,n):
r = [float('-inf')]*(n+1) # Inicializa r con -infinito para todas las posiciones
r[0] = 0 # El valor máximo para una varilla de longitud 0 es 0
for j in range(1,n+1): # para incrementar la longitud j de la varilla
q = float('-inf')
for i in range(j): # i es la posición del primer corte
q = max(q,p[i]+r[j-i-1])
r[j] = q # recordá el valor de la solución para la longitud j
return r[n]
```
```bash
# Ejemplo de uso
p = [i for i in range(1, 41)] # Ejemplo de precios
n = 40 # Longitud de la varilla
The maximum obtainable price is: 40
The execution time was: 0.0003399848937988281 seconds
```
## Ejercicio LCS
- Longest common sub-sequence.
- Dadas dos secuencias, encontrar la longitud de la subsecuencia más larga presente en ambas. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente de manera contigua. Por ejemplo, "abc", "abg", "bdf", "aeg", "acefg", etc. son subsecuencias de "abcdefg". De forma más formal, si tenemos dos secuencias X e Y, una secuencia Z será una subsecuencia de X y Y si Z puede obtenerse eliminando cero o más elementos de X y Y sin cambiar el orden de los elementos restantes.
- Ejemplo:
- Entrada: Secuencia A = "AGGTAB", Secuencia B = "GXTXAYB"
- Salida: Longitud de la subsecuencia más larga en común = 4, Subsecuencia común más larga = "GTAB"
- Dada una secunecia X = < $x_1, x_2, ..., x_m$ >
- Definimos el i esimo prefijo de X `for i = 0,1,...m`
- como $X_i$ = $<x_1,x_2,...,x_i>$.
- Por ejemplo si X = <A,B,C,B,D,A,B>
- entonces $X_4$ = <A,B,C,B> y $X_0$ es la secuencia vacía
### Teorema 14.1: Sub estructura optima para LCS
- siendo $X = x_1,...,x_m$ e Y lo mismo $Y = y_1, ..., y_n$ secuencias y sea $Z = z_1, ... z_k$ cualquier LCS entre $X,Y$
1. Sí $x_m$ = $y_n$ entonces $z_k$ = $x_m$ = $y_n$ y $Z_{k-1}$ es una LCS de $X_{m-1}$ y $X_{n-1}$
2. Sí $x_m \neq y_n$ y $z_k \neq x_m$ entonces $Z$ es una LCS de $X_{m-1}$ e $Y$
3. Sí $x_m \neq y_n$ y además $z_k \neq y_n$, entonces $Z$ es una LCS de X y de $Y_{n-1}$
### Demostración
- (1) sí $z_k$ = $x_m$ entonces podemos appendear $x_m = y_n$ a $Z$ para obtener una subsecuencia en común de $X$ e $Y$ de longitud $k+1$ contradiciendo la suposición que $Z$ es la LCS de $X$ e $Y$, por lo tanto debemos de tener que $z_k$ = $x_m$ = $y_n$.
- Ahora, $Z_{k-1}$ es de longitud $k-1$ subsecuencia de X_{m-1} y $Y_{n-1}$. Ahora deseamos poder mostrar que esa es la LCS.
- Supongamos que para el proposito de la demostración por absurdo que existe una subsecuencia en común $W$ de $X_{m-1}$ y $Y_{n-1}$ con longitud mayor a $k-1$, entonces appendeando $x_m = y_n$ a $W$ produce una subsecuencia en común entre $X$ e $Y$ cuya longitud es mayor a $k$, y **esto es una contradicción**.
- (2) si $z_k \neq x_m$ entonces $Z$ es una subsecuencia en común de $X_{m-1}$ e $Y$. Sí ahí hubiera una subsecuencia en común $W$ de $X_{m-1}$ e $Y$ con longitud mayor a $k$, entonces $W$ podría tambien ser una subsecuencia en común de $X_m$ e $Y$, contradiciendo la aasumición de que $Z$ es una LCS de $X$ e $Y$.
- (3) La demostración es simetrica a (2). $\ \ \ \ \square$