# Programación Dinámica
###### tags: `temas 2do Parcial`
## Resumen
### Glosario/definiciones
### Trucos
* Pensar las N posibilidades que tenemos en cada paso de la recursión
* Si hacemos mín sobre la recursión, podemos usar +infinito para filtrar resultados o para los valores no-definidos (lo mismo con máx y -infinito)
* "minimtoria" (simil sumatoria/productoria) (ver ejercicio corte de vara / rod cutting)
### Errores comunes
* Olvidarse el +1 en la recursión
* Olvidarse de devolver el resultado memoizado si ya está seteado
* Olvidarse del return en el algoritmo
## Ejercicios de la guia 1, sección "Programación dinámica (y su relación con backtracking"
### 5. Subset sum
Salteado porque el enunciado spoilea la función, los algoritmos y la complejidad
### 6. Coin change
#### Función recursiva
Suponemos que el problema siempre tiene solución (alcanzan los billetes)
$B = \{b_1, ..., b_n\}$
$cc(i, c) =$
\begin{cases}
∅ & \text{si $i = 0 ∧ c ≤ 0$} \\
B & \text{si $i = 0 ∧ 0 < c$} \\
\arg\min_{\#}( \\
\ cc(i-1, c - B_i) ∪ B_i, \\
\ cc(i-1, c) \\
) & \text{sino}
\end{cases}
#### Algoritmo
```python
# B = {b1, ..., bn}
B = {2, 3, 5, 10, 20, 20}
UNDEFINED = {-1}
M[B.size()][UNDEFINED for i in range(0, c)]
def cc(i ,c): # coin change
if (M[i][c] != UNDEFINED):
return M[i][c]
if (i == 0 and c ≤ 0):
M[i][c] = {}
elif (i == 0 and 0 < c):
M[i][c] = B
else:
M[i][c] = argmin(size(),
cc(i-1, c - B[i]).union(B[i]),
cc(i-1, c)
)
return M[i][c]
cc(B.size() - 1, 14)
```
#### Complejidad
$O(n²c)$
Porque la estructura de memoización tiene tamaño $O(nc)$ pero copiar los conjuntos a cada posición es $O(n)$.
### 7. Astro Void
#### Función
$p = {p1, p2, ..., pn}$
i: índice en p
a: cantidad de asteroides
n: tamaño de p
av: saldo
$av(i, a) =$
\begin{cases}
0, & \text{ si } i < 0 \\
\max( \\
\ -p[i] + av(i-1, a+1), &&\text{// compra} \\
\ av(i-1, a) &&\text{// ninguna operación} \\
), & \text{ si } a = 0 \\
\max( \\
\ p[i] + av(i-1, a-1), &&\text{// venta} \\
\ -p[i] + av(i-1, a+1), &&\text{// compra} \\
\ av(i-1, a) &&\text{// ninguna operación} \\
), & sino
\end{cases}
$av(n-1, 0)$ // para resolver
#### Algoritmo
```python
P = (3, 2, 5, 6)
def av(i, a):
if M[i][a] != -infinity:
return M[i][a]
elif (i < 0):
M[i][a] = 0
elif (a == 0): # si no tengo asteroides, solo puedo comprar o seguir de largo
M[i][a] = max(-p[i] + av(i-1, a+1), # compra
av(i-1, a) # no compro ni vendo
)
else:
M[i][a] = max(p[i] + av(i-1, a-1), # vende
-p[i] + av(i-1, a+1), # compra
av(i-1, a) # no compro ni vendo
)
return M[i][a]
```
#### Complejidad
$O(n²)$ por el tamaño de la matriz (tamaño del vector al cuadrado) y porque completar cada posición es $O(1)$.
### Corte de vara / Rod cutting
#### Fórmula
Cortes: $L = (2, 4, 7)$
Longitud: $l = 10$
s: start
c: cut
e: end
rc: total rod cutting cost
Definimos $L' = (0, 2, 4, 7, l) = (0, 2, 4, 7, 10)$
$rc(s, e) = e - s + \min_{c \in L' \\ s < c < e} ( rc(s, c) + rc(c, e) )$
Llamado que resuelve el problema: $rc(0, |L'| - 1)$
#### Algoritmo
```python
L_prima = [0, 2, 4, 7, 10]
min_cut = INFINITY
M[L_prima.size()][INFINITY for i in range(0, L_prima.size())]
def rc(s, e):
if M[s][e] != INFINITY:
return M[s][e]
for c in L_prima:
min_cut = min(min_cut, rc(s, c) + rc(c, e))
return M[s][e] = e-s + min_cut
return M[s][e]
```
#### Complejidad
$O(n³)$
($O(n²)$ por el tamaño de la matriz de memoización y $O(n)$ por el costo computacional de cada nodo)
### 9: terreno pociones trampas vida mínima
#### Fórmula
#### Algoritmo
#### Complejidad
la matriz
### 10: apilar cajas
#### Fórmula
w: pesos
$w = [19, 7, 5, 6, 1]$
s: soporte
$s = [15, 13, 7, 8, 2]$
$N$: cantidad de cajas
$s'$: soporte de la caja de menor soporte (eslabón más débil/reactivo limitante)
$ac(i, s') =$
\begin{cases}
0, && \text{si } i = N \\
ac(i+1, s'), && \text{si la caja } i \text{ no es apilable}\\
\max( &ac(i+1, \min(s' - w[i], s[i]) ) + 1,\\
&ac(i+1, s' ) ),& \text{si la caja } i \text{ es apilable}
\end{cases}
$ac(0, +inf)$
$apilable(i, s') = 0 < s' - w[i]$
#### Algoritmo
```python
UNDEFINED = -infinity
M[w.size()][UNDEFINED for i in range(0, w.size())]
def ac(i, sp):
if M[i][sp] != UNDEFINED
return M[i][sp]
if i == N:
return 0
if apilable(i, sp):
M[i][sp] = ac(i+1, sp)
else:
M[i][sp] = max( ac(i+1, min(sp - w[i], s[i]) + 1 ),
ac(i+1, sp ))
return M[i][sp]
def apilable(i, sp):
return 0 < sp - w[i]
ac(0, infinity)
```
#### Complejidad
tamaño de la matriz
### 11: Intercalar operaciones al vector
**TODO: CONSULTAR**
#### Fórmula
Hacemos versión de decisión
$f(v, w, i, w_a) =$
\begin{cases}
True, && \text{si $i = |v|-1 ∧ w = w_a$} \\
False, && \text{si $i = |v|-1 ∧ w ≠ w_a$} \\
f(v, w, i, w_a + v_{i+1}) ∨ f(v, w, i, w_a * v_{i+1}) ∨ f(v, w, i, w_a ↑ v_{i+1}), && \text{caso contrario} \\
\end{cases}
#### Algoritmo
No anda :(
```python
v = [3, 1, 5, 2, 1]
w = 400
UNDEFINED = -999
M = [[UNDEFINED for _ in range(len(v))] for _ in range(w)]
def f(i, w_a):
print(i, w_a)
if (i == len(v)-1 and w_a == w):
return True
if (i == len(v)-1 and w_a != w):
return False
if (type(M[i][w_a]) == type(True)):
return M[i][w_a]
else:
if (w < w_a + v[i+1]):
M[i][w] = False
else:
M[i][w_a + v[i+1]] = f(i+1, w_a + v[i])
if (w < w_a * v[i+1]):
M[i][w] = False
else:
M[i][w_a * v[i+1]] = f(i+1, w_a * v[i])
if (w < w_a ** v[i+1]):
M[i][w] = False
else:
M[i][w_a ** v[i+1]] = f(i+1, w_a ** v[i])
return operation_in_range(w_a, i, '+') or operation_in_range(w_a, i, '*') or operation_in_range(w_a, i, '**')
print(f(0, v[0]))
def operation_in_range(w_a, i, op):
if (op == '+'):
if (w < w_a):
M[i][w] = False
return M[i][w]
else:
M[i][w_a] = f(i+1, w_a + v[i])
return M[i][w_a]
if (op == '*'):
if (w < w_a):
M[i][w] = False
return M[i][w]
else:
M[i][w_a] = f(i+1, w_a * v[i])
return M[i][w_a]
if (op == '**'):
if (w < w_a):
M[i][w] = False
return M[i][w]
else:
M[i][w_a] = f(i+1, w_a ** v[i])
return M[i][w_a]
```
#### Complejidad
Sign in with Wallet
Connect another wallet