# TDA | Practica 1 ejercicio 8
$\textbf{Cortes Económicos}$
$\text{8. Debemos cortar una vara de madera en varios lugares predeterminados. Sabemos que el costo de realizar un corte en una madera de longitud } \ell \text{ es } \ell \text{ (y luego de realizar ese corte quedarán 2 varas de longitudes que sumarán } \ell \text{). Por ejemplo, si tenemos una vara de longitud 10 metros que debe ser cortada a los 2, 4 y 7 metros desde un extremo, entonces los cortes se pueden realizar, entre otras maneras, de las siguientes formas:}$
$\text{Primero cortar en la posición 2, después en la 4 y después en la 7. Esta resulta en un costo de } 10 + 8 + 6 = 24 \text{ porque el primer corte se hizo en una vara de longitud 10 metros, el segundo en una de 8 metros y el último en una de 6 metros.}$
$\text{Cortar primero donde dice 4, después donde dice 2, y finalmente donde dice 7, con un costo de } 10 + 4 + 6 = 20, \text{ que es menor.}$
$\text{Queremos encontrar el mínimo costo posible de cortar una vara de longitud } \ell.$
$\text{(a) Convencerse de que el mínimo costo de cortar una vara que abarca desde } i \text{ hasta } j \text{ con el conjunto } C \text{ de lugares de corte es } j - i \text{ más el mínimo, para todo lugar de corte } c \text{ entre } i \text{ y } j, \text{ de la suma entre el mínimo costo desde } i \text{ hasta } c \text{ y el mínimo costo desde } c \text{ hasta } j.$
$\text{(b) Escribir matemáticamente una formulación recursiva basada en (a). Explicar su semántica e indicar cuáles serían los parámetros para resolver el problema.}$
$\text{(c) Diseñar un algoritmo de PD y dar su complejidad temporal y espacial auxiliar. Comparar cómo resultaría un enfoque top-down con uno bottom-up.}$
$\text{(d) Supongamos que se ordenan los elementos de } C \text{ en un vector cortes y se agrega un 0 al principio y un } \ell \text{ al final. Luego, se considera que el mínimo costo para cortar desde el } i\text{-ésimo punto de corte en cortes hasta el } j\text{-ésimo punto de corte será el resultado buscado si } i = 1 \text{ y } j = |C| + 2.$
$\text{I) Escribir una formulación recursiva con dos parámetros que esté basada en (d) y explicar su semántica.}$
$\text{II) Diseñar un algoritmo de PD, dar su complejidad temporal y espacial auxiliar y compararlas con aquellas de (c). Comparar cómo resultaría un enfoque top-down con uno bottom-up.}$
## Resolución
## a)
- Queremos optimizar el costo, o sea que sea lo mínimo posible.
- Hay que buscar el minimo para todo punto del conjunto estando acotado por i, y j, siendo i el inicio y j el fin.
- Considerar todas las maneras posibles de realizar los cortes y elegir la que cueste menos
## b)
- Sea $C$ un conjunto de cortes a realizar sobre la vara $\ell_i$, $C_i$ un corte especifico en este conjunto $C =$ {$c_1,c_2,...c_n$} y $0<c_1<c_2<...<c_n<\ell$ el costo de realizar un corte sobre la vara de longitud $\ell$ es $\ell$
$C_0 = 0 \\
C_{n+1} = \ell \\
MC(i, j) = \begin{cases}
0 & \text{si } j = i+1 \\
\min_{i < k < j} \left( MC(i, k) + MC(k, j) + (C_j - C_i) \right) & \text{si } j > i+1
\end{cases}$
## c-d)
### Enfoque top-down
```python
from typing import List
def M(longitud: int, cortes: List[int]) -> int:
cortes = [0] + cortes + [longitud] # Como dice el inciso d
memo = {}
def costoMinimo(i: int, j: int) -> int:
if j <= i + 1:
return 0
if (i, j) in memo: # Caso base si el resultado ya está memoizado
return memo[(i, j)]
costoMin = float('inf')
for k in range(i + 1, j): # Paso recursivo
costoActual = costoMinimo(i, k) + costoMinimo(k, j) + (cortes[j] - cortes[i])
costoMin = min(costoMin, costoActual)
memo[(i, j)] = costoMin # Guardo resultado en memoria
return costoMin
# realiza la llamada inicial a la función recursiva
return costoMinimo(0, len(cortes) - 1)
# Ejemplo de uso
longitudVara = 10
cortes = [2, 4, 7]
print(M(longitudVara, cortes))
```
## Arbol
#### Idea de lo que sería el arbol con memoización.
- En realidad cada nodo tendría una cierta cantidad de aristas por la iteración de $k$
### COMPLEJIDAD
- Eric:
- La cantidad de subproblemas unicos es ${|C|}\choose{2}$.
- $\frac{|C|}{2!(|C|-k)}$ $\leq$ $|C|^2$ Entonces podemos tomar esta cota.
- Entonces podemos decir que la cantidad de nodos unicos van a ser $|C|^2$.
- Ahora: Hay dos llamadas recursivas por cada iteración de k.
- Esto significa que en peor caso va a recorrer la totalidad en cada iteración que es $2 \times |C|$
- Entonces sabemos que:
- #NodosUnicos ~ $|C|^2$
- #NodosMemo ~ $O(1)$
- #HijosDeNodosUnicos ~ $2 \times |C| \times |C|^2$ = $|C|^3$
- max(#NodosUnicos, #NodosMemo, #HijosDeNodosUnicos) = $|C|^3|
- $\Rightarrow$ $\therefore$ $O(n^3)$
- ~~Tengo entendido que hablando de complejidad temporal por cada hijo se abren dos hojas excepto si ya está precalculado, lo cual iría a $memo$~~
- ~~A simple vista veo una complejidad de $O(n^2)$~~
- ~~Pero tengo entendido que es cuadratica y no lo veo del todo.~~
- ~~Para n cortes hay O(n²) pares (i,j) posibles, pero para cada subproblema toma ua decisión sobre cada punto de corte posible (i,j) lo cual es proporcoinal a n.~~
- ~~La complejidad de un problema unico es $O(n)$~~
### Complejidad espacial
- ToDo
- Estimo cuadratica