# Ejercicio 5 practica 1 ### Ejercicio 5: Problema de la Suma de Subconjuntos usando Programación Dinámica ## Consigna En este ejercicio, vamos a resolver el problema de la suma de subconjuntos utilizando la técnica de programación dinámica. a) Sea $n = |C|$ la cantidad de elementos de $C$. Considerar la siguiente función recursiva $ss'_{C} : \{0, \ldots , n\} \times \{0, \ldots , k\} \rightarrow \{V, F\}$ (donde $V$ indica verdadero y $F$ falso) tal que: $$ ss'_{C}(i, j) = \begin{cases} j = 0 & \text{si } i = 0\\ ss'_{C}(i- 1, j) & \text{si } i \neq 0 \land C[i] > j\\ ss'_{C}(i- 1, j) \lor ss'_{C}(i- 1, j - C[i]) & \text{si no} \end{cases} $$ Convencerse de que esta es una definición equivalente de la función $ss$ del inciso e) del Ejercicio 1, observando que $ss(C, k) = ss'_{C}(n, k)$. En otras palabras, convencerse de que el algoritmo del inciso f) es una implementación por backtracking de la función $ss'_{C}$. Concluir, pues, que $O(2^n)$ llamadas recursivas de $ss'_{C}$ son suficientes para resolver el problema. b) Observar que, como $C$ no cambia entre llamadas recursivas, existen $O(nk)$ posibles entradas para $ss'_{C}$. Concluir que, si $k \ll 2^n/n$, entonces necesariamente algunas instancias de $ss'_{C}$ son calculadas muchas veces por el algoritmo del inciso f). Mostrar un ejemplo donde se calcule varias veces la misma instancia. c) Considerar la estructura de memoización (i.e., el diccionario) $M$ implementada como una matriz de $(n+ 1) \times (k+ 1)$ tal que $M[i, j]$ o bien tiene un valor indefinido $\bot$ o bien tiene el valor $ss'_{C}(i, j)$, para todo $0 \leq i \leq n$ y $0 \leq j \leq k$. Convencerse de que el siguiente algoritmo top-down mantiene un estado válido para $M$ y computa $M[i, j] = ss'_{C}(i, j)$ cuando se invoca $ss'_{C}(i, j)$. 1. Inicializar $M[i, j] = \bot$ para todo $0 \leq i \leq n$ y $0 \leq j \leq k$. 1. subset_sum($C, i, j$): // implementa $ss({c_1, \ldots , c_i}, j) = ss'_{C}(i, j)$ usando memoización 1. Si $j < 0$, retornar falso 1. Si $i = 0$, retornar $(j = 0)$ 1. Si $M[i, j] = \bot$: 1. Poner $M[i, j] = \text{subset_sum}(C, i- 1, j) \lor \text{subset_sum}(C, i- 1, j - C[i])$ 1. Retornar $M[i, j]$ d) Concluir que $\text{subset_sum}(C, n, k)$ resuelve el problema. Calcular la complejidad y compararla con el algoritmo $\text{subset_sum}$ del inciso f) del Ejercicio 1. ¿Cuál algoritmo es mejor cuando $k \ll 2^n$? ¿Y cuándo $k \gg 2^n$? e) Supongamos que queremos computar todos los valores de $M$. Una vez computados, por definición, obtenemos que $$ M[i, j] = ss'_{C}(i, j) $$ $$ ss' = ss'_{C}(i- 1, j) \lor ss'_{C}(i- 1, j - C[i]) $$ $$ = M[i- 1, j] \lor M[i- 1, j - C[i]] $$ cuando $i > 0$, asumiendo que $M[i- 1, j-C[i]]$ es falso cuando $j-C[i] < 0$. Por otra parte, $M[0, 0]$ es verdadero, mientras que $M[0, j]$ es falso para $j > 0$. A partir de esta observación, concluir que el siguiente algoritmo bottom-up computa $M$ correctamente y, por lo tanto, $M[i, j]$ contiene la respuesta al problema de la suma para todo $\{c_1, \ldots , c_i\}$ y $j$. 1) subset_sum(C, k): // computa M [i, j] para todo 0 ≤ i ≤ n y 0 ≤ j ≤ k. 2) Inicializar M [0, j] := (j = 0) para todo 0 ≤ j ≤ k. 3) Para i = 1, . . . , n y para j = 0, . . . , k: 4) Poner M [i, j] := M [i − 1, j] ∨ (j − C[i] ≥ 0 ∧ M [i − 1, j − C[i]]) ## Resolución - Recordar como es la suma de subconjuntos - Que querías sumar hasta llegar a un $k$, etc, etc. ## a) - Tiene sentido, pues eseta función recursiva es igual a la implementación del inciso 1_F. ## b) - Tomemos el ejemplo de $C= ${$6,12,6$} y al número que queremos llegar es 12. Si vemos el arbol de recursión se repiten varios calculos.  Recomiendo tocar click derecho y abrir en una nueva ventana par auna mejor vista  - Al hacer una busqueda exhaustiva, explora las mismas opciones y las vuelve a chequear. - Otro ejemplo puede ser $C$ = {6,12,6,7,7,7} con $k=19$ - el algoritmo de backtracking va a hacer varias sumas parciales mas de una vez ## c) - El paso 6 del algoritmo es crucial ya que evita recalculaciones innecesarias del algoritmo $(n+1) \times (k+1)$ ## d) - El algoritmo es capaz de identificar si existe un subconjunto $C$ que sume exactamente $k$   - Hay $n \times k$ subproblemas unicos, y por su tabla de memoizacoin es de $(n+1) \times (k+1)$. - la complejidad temporal es el producto total de subproblemas por el trabajo realizado por subproblema unico. - por cada $n$ se podría sumar desde 0 hasta $k$ $O(n \times k)$. - El algoritmo es definitivamente mejor con programación dinamica. - O sea cuando $k << 2^n$ porque el número de subproblemas unicos a resolver es menor. - Pero si $k$ es mas grande que $2^n$ $\Rightarrow$ $O(n \times k)$ va a ser mucho mas mayor. ## e) - Lo que se nos está diciendo es que este algoritmo iterativo es equivalente al algoritmo top-down recursivo. ## f-g) - [resolución](https://www.youtube.com/watch?v=dQw4w9WgXcQ&pp=ygUXbmV2ZXIgZ29ubmEgZ2l2ZSB5b3UgdXA%3D)