Skip to content

Instantly share code, notes, and snippets.

@FdelMazo

FdelMazo/TallerProgramacionDinamica.ipynb

Last active October 10, 2019 15:45
Show Gist options
  • Save FdelMazo/691bdff48a9a4ecbc5d768b45b048b93 to your computer and use it in GitHub Desktop.
Save FdelMazo/691bdff48a9a4ecbc5d768b45b048b93 to your computer and use it in GitHub Desktop.
Download ZIP
Programación Dinámica: or How I Learned to Stop Worrying and Love the Recurrencia
Display the source blob
Display the rendered blob
Raw
TallerProgramacionDinamica.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Programación Dinámica: or How I Learned to Stop Worrying and Love the Recurrencia\n",
"\n",
"La programación dinámica es una técnica de diseño de algoritmos. En los términos más básicos puede reducirse a **resolver un problema en base a subproblemas anteriores.** \n",
"\n",
"## Cuándo puedo usar PD?\n",
"\n",
" Siempre que un problema se pueda dividir en una secuencia de subproblemas y la solución a cada uno de estos subproblemas sirva para llegar a la solución del problema original.\n",
" \n",
"## Cuándo me conviene usar PD?\n",
"\n",
"* Superposición de subproblemas: Las soluciones a los subproblemas se necesitan varias veces, no solo para resolver el siguiente.\n",
"\n",
"* Subestructura óptima: Se puede llegar a la solución óptima del problema usando como base las soluciones óptimas a los subproblemas."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Tipos de PD:\n",
"* Top Down (memoization): Empezando desde mi problema, cada vez que voy a utilizar un resultado anterior me pregunto si ya lo tengo guardado. Si no lo esta, lo genero y lo guardo en memoria\n",
"\n",
"* Bottom Up (tabulation): Empezando desde el problema más chico posible, itero todos los subproblemas. Así, siempre voy a tener toda la información guardada (a costo de espacio). Una vez que llego al problema original, resuelvo teniendo en cuenta lo anterior. --> **Este es el visto en este taller**"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Pasos para resolver cualquier tipo de problema (Bottom Up)\n",
"\n",
"Quiero sacar el factorial de 5. El factorial de 5 es 5 multiplicado al factorial de 4. El factorial de 4 es 4 multiplicado al factorial de 3... etc. \n",
"\n",
"La estrategia es la de guardar cada uno de esos resultados en una lista incremental (`DP`) donde cada elemento es la solución al problema en ese indice. Siguiendo el ejemplo, en `DP[1]` guardo el factorial de 1; en `DP[2]` guardo el factorial de 2; así, hasta llegar a `DP[5]`, que es el problema a resolver.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Ecuación de recurrencia \n",
"\n",
"La ecuación de recurrencia se compone de dos partes\n",
"\n",
"1. Valores Iniciales $DP_0$: Cuál es el problema más chico posible y cuál es su solución? (En analogía a D&C, esto es 'el caso base')\n",
"\n",
"2. Relación de recurrencia $DP[i]$: Cómo se relaciona una solución con las soluciones previas? (Pueden ser muchos casos distintos)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$DP_0 = \\text{Valor Inicial}$$\n",
"\n",
"\\begin{equation}\n",
" DP[i]=\\begin{cases}\n",
" \\text{Relación de recurrencia (caso 1)} & \\text{if condición}. \\\\\n",
" \\text{Relación de recurrencia (caso 2)} & \\text{if otra condición}. \\\\\n",
" \\text{...} & \\text{...}. \\\\\n",
" \\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Ejemplo: Factorial de x\n",
"\n",
"### Puedo usar PD?\n",
"\n",
"Si: el factorial de x depende del factorial de x-1. Todo problema depende de la solución del problema anterior.\n",
"\n",
"### Ecuación de recurrencia\n",
"\n",
"* Cuáles son mis valores iniciales?\n",
" * Factorial de 0 = 1\n",
" * Factorial de 1 = 1\n",
" \n",
"* Cuál es mi relación de recurrencia? \n",
" * Factorial de i = i * factorial de i-1"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"$$DP[0] = 1 \\\\ DP[1] = 1$$\n",
"\n",
"\\begin{equation}\n",
" DP[i]=\\begin{cases}\n",
" i * DP[i-1]\n",
" \\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 1, 2, 6, 24, 120]\n"
]
},
{
"data": {
"text/plain": [
"120"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def factorial(x):\n",
" dp = [None] * (x+1)\n",
" dp[0] = 1\n",
" dp[1] = 1\n",
" for i in range(2, len(dp)):\n",
" dp[i] = dp[i-1] * i\n",
" print(dp)\n",
" return dp[x]\n",
"\n",
"factorial(5)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"**Complejidad: $O(n)$** "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Código -> Creo, seteo, recorro, resuelvo, devuelvo\n",
"\n",
"1. Creo una lista (o diccionario) del tamaño de problemas que voy a tener donde guardo los resultados.\n",
"\n",
" * Tengo un arreglo de longitud n --> Tengo n problemas\n",
"\n",
" * Tengo que resolver como hacer algo la 5ta vez --> Tengo 5 problemas\n",
"\n",
"2. Seteo los valores iniciales. \n",
"\n",
"3. Recorro el resto de mis problemas (pensar que los iniciales ya estan resueltos).\n",
"\n",
"4. Resuelvo mis problemas, con la ecuación de recurrencia.\n",
"\n",
"5. Devuelvo lo pedido."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Problema 0: Buscar el máximo de un arreglo\n",
"\n",
"### Ecuación de recurrencia\n",
"\n",
"* Cuáles son mis valores iniciales? \n",
" * Mi problema más chico: Una lista de longitud 1\n",
" * Maximo de [3] es 3\n",
" <br>**Valor inicial: DP[0] = arr[0]**\n",
" \n",
" \n",
"* Cuál es mi relación de recurrencia? \n",
" * El elemento anterior a mi es mas grande que yo\n",
" <br>**Relación de Recurrencia (caso 1): DP[i] = DP[i-1]**\n",
"\n",
" * Soy mas grande que mi elemento anterior\n",
" <br>**Relación de Recurrencia (caso 2): DP[i] = arr[i]**"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"$$DP[0] = arr[0]$$\n",
"\n",
"\\begin{equation}\n",
" DP[i]=\\begin{cases}\n",
" arr[i] & \\text{if arr[i] > DP[i-1]}\\\\ \\\\\n",
" DP[i-1] & \\text{if DP[i-1] > arr[i]}\n",
"\\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 5, 5]\n",
"[1, 5, 5, 5, 5, 21, 21, 21]\n"
]
},
{
"data": {
"text/plain": [
"21"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def maximo(arr):\n",
" dp = [None] * len(arr) #Creo\n",
" dp[0] = arr[0] #Seteo\n",
" for i in range(1,len(dp)): #Recorro\n",
" if arr[i] > dp[i-1]:\n",
" dp[i] = arr[i]\n",
" if dp[i-1] > arr[i]:\n",
" dp[i] = dp[i-1] #Resuelvo\n",
" print(dp)\n",
" return dp[-1] #Devuelvo\n",
"\n",
"maximo([1,5,2])\n",
"maximo([1,5,2,3,-2,21,10,3])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"**Complejidad: $O(n)$** "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Tips y cuidados!!\n",
"\n",
"* El caso base suele ser 0, 1, infinito, o el arreglo mismo.\n",
"\n",
"* Se pueden inicializar todos los problemas directamente en el caso base (luego van pisando las soluciones), así se evita el paso de seteo.\n",
"\n",
" ```\n",
" Si el caso base es el arreglo mismo: dp = copy.copy(arr)\n",
" Si el caso base es 0: dp = [0] * len(arr)\n",
" Si el caso base es 1: dp = [1] * len(arr)\n",
" Si el caso base es infinito: dp = [math.inf] * len(arr)\n",
" ``` "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"* Ojo! No siempre tengo que devolver el último resultado:\n",
" * Encontrar la maxima ganancia para 100 ventas --> Me piden el resultado en 100\n",
" * Encontrar la maxima ganancia para cualquier venta, hasta 100 --> Me piden el maximo de mis resultados\n",
" \n",
"* La devolucion suele ser: `min(dp), max(dp), dp[-1], dp[0]`"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"21"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from copy import copy\n",
"def maximo_refactorizado(arr):\n",
" dp = copy(arr) #Creo\n",
" for i in range(1,len(dp)): #Recorro\n",
" dp[i] = max(arr[i],dp[i-1]) #Resuelvo\n",
" return dp[-1] #Devuelvo\n",
"\n",
"maximo_refactorizado([1,5,2,3,-2,21,10,3])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"---\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Problema 1: Fibonacci\n",
"\n",
"> Se llaman números de Fibonacci a aquellos que forman parte de la sucesión infinita de números naturales donde cada número se calcula sumando los dos anteriores a él. \n",
"\n",
"Esta sucesión fue descrita por Fibonacci como la solución a un problema de cría de conejos: \n",
"\n",
"> “Cierto hombre tiene una pareja de conejos juntos en un lugar cerrado y desea saber cuántos son creados a partir de este par en un año cuando, de acuerdo a su naturaleza, cada pareja necesita un mes para envejecer y cada mes posterior procrea otra pareja” "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"$$DP[0] = 1 \\\\ DP[1] = 1$$\n",
"\n",
"\\begin{equation}\n",
" DP[i]=\\begin{cases}\n",
" DP[i-1]+DP[i-2] & \n",
" \\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def fibonacci(n):\n",
" dp = [1] * n\n",
" for i in range(2,len(dp)):\n",
" dp[i] = dp[i-1]+dp[i-2]\n",
" return dp\n",
"\n",
"fibonacci(10)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"**Complejidad: $O(n)$** "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Problema 2: Longest Contiguous Increasing Subsequence\n",
"\n",
"> Dado un arreglo, encontrar la longitud del mayor subarreglo incremental contiguo. \n",
"\n",
"Por ejemplo: `LCIS([1, 8, 4, 2, 1])` --> Devuelve 2, que es la longitud del subarreglo `[1,8]`"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"$$DP[0] = 1$$\n",
"\n",
"\\begin{equation}\n",
" DP[i]=\\begin{cases}\n",
" DP[i-1]+1 & \\text{if \\(arr[i-1]<arr[i]\\) }\\\\ \\\\\n",
" 1 & \\text{else}\\\\\n",
"\\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 2, 1, 1, 1]\n"
]
},
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def LCIS(arr):\n",
" dp = [1] * len(arr)\n",
" for i in range(1,len(dp)):\n",
" if arr[i-1] < arr[i]: \n",
" dp[i] = dp[i-1]+1\n",
" print(dp)\n",
" return max(dp)\n",
"\n",
"LCIS([1, 8, 4, 2, 1])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"**Complejidad: $O(n)$** "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Problema 3: Mayor suma de subarreglo contiguo \n",
"\n",
"> Dado un arreglo, encontrar el valor máximo posible para la suma de un subarreglo contiguo\n",
"\n",
"Ej: `sumatoria_ventana([−2, 1, −3, 4, −1, 2, 1, −5, 4])` --> Devuelve 6, de sumar `[4, −1, 2, 1]`"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"$$DP[0] = arr[0]$$\n",
"\n",
"\\begin{equation}\n",
" DP[i]=\\begin{cases}\n",
" DP[i-1]+arr[i] & \\text{if (DP[i-1]+arr[i] > arr[i])} \\\\ \\\\\n",
" arr[i] & \\text{else}\n",
"\\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[-2, 1, -2, 4, 3, 5, 6, 1, 5]\n"
]
},
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def sumatoria_ventana(arr):\n",
" dp = copy(arr)\n",
" for i in range(1,len(dp)):\n",
" dp[i] = max(dp[i-1]+arr[i],arr[i])\n",
" print(dp)\n",
" return max(dp)\n",
"\n",
"sumatoria_ventana([-2, 1, -3, 4, -1, 2, 1, -5, 4])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"**Complejidad: $O(n)$** "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Problema 4: Cortando una Soga <br>[CLRS (Thomas Cormen - Introduction to Algorithms) 15.1]\n",
"\n",
">Dada una soga de n centimetros y un arreglo de a cuanto se puede vender cada soga mas chica que ella, encontrar la mayor ganancia que puedo obtener de vender la soga, teniendo en cuenta que puedo cortarla todas las veces que quiero.\n",
"\n",
"Ej: Para una soga de 4 centimetros con precios `[0,1,5,8,9]` (es decir, una soga de 1cm se vende a 1 peso, una de 2cm a 5 pesos, etc), el valor máximo que puedo obtener es 10, cortandola en 2 y vendiendo dos sogas de 2cm cada una."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"$$DP[0] = arr[0]$$ \n",
"$$\\text{(ya que toda soga la puedo vender por su precio original)}$$ \n",
"\n",
"\\begin{equation}\n",
" DP[i]=\\begin{cases}\n",
" max(DP[i-j]+precios[j]) & \\forall j \\in [0, i) \\\\ \\\\\n",
" arr[i] & \\text{else}\n",
"\\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0, 1, 5, 8, 10]\n"
]
},
{
"data": {
"text/plain": [
"10"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def cortar_soga(precios,n):\n",
" dp = copy(precios[:n+1])\n",
" for i in range(1, n+1):\n",
" for j in range(i):\n",
" dp[i] = max(dp[i],precios[j]+ dp[i-j])\n",
" print(dp)\n",
" return dp[-1]\n",
"\n",
"cortar_soga([0, 1, 5, 8, 9,10],4)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"**Complejidad: $O(n^2)$** "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Problema 5: El problema del cambio <br> [KT (Kleinberg Tardos - Algorithm Design) 6.4]\n",
"\n",
"> Dado un arreglo de valores de monedas, y un valor N, encontrar la menor cantidad de monedas necesarias para representar N.\n",
"\n",
"Ej: Para 4 pesos y monedas de 1, 2 y 3, la solucion es 2: dar dos monedas de 2. Para 3 pesos, la solucion es 1, solo dar la moneda de 3."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"\\begin{equation}\n",
" DP[i]=\\begin{cases}\n",
" 1 & \\text{if moneda de i existe}. \\\\ \\\\\n",
" \\text{\\(min(DP[i-m]+1)\\)} & \\forall m \\in M \\\\\n",
"\\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1\n",
"2\n"
]
}
],
"source": [
"from math import inf\n",
"\n",
"def cambio(M, n):\n",
" dp = [inf]*(n+1)\n",
" for i in range(n+1):\n",
" for moneda in M:\n",
" if i == moneda:\n",
" dp[i] = 1\n",
" if i > moneda:\n",
" dp[i] = min(dp[i], dp[i - moneda] + 1)\n",
" return dp[n]\n",
"\n",
"print(cambio([1,2,3], 3))\n",
"print(cambio([1,2,3], 4))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"**Complejidad: $O(n * K)$ siendo K la cantidad de monedas** "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Matrices: Problemas con dos parametros o más\n",
"\n",
"Hasta ahora solo hicimos problemas donde se tenga en cuenta un solo parametro. Es por eso que veníamos trabajando con lista de resultados. Cual es mi solución en 1, en 2, en 3... en i. Pero, y si tengo dos parametros variables? Cual es mi solución en i,j?\n",
"\n",
"\\begin{equation}\n",
" DP(i,j)=\\begin{cases}\n",
" ... & ... \\\\\n",
" ... & ...\n",
"\\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Problema 6: Subset Sum [KT 6.4]\n",
"\n",
"> Dado un arreglo y un número `suma`, devolver verdadero si existe un subconjunto que sume exactamente `suma`.\n",
"\n",
"Ej: Puedo sumar 9 con el arreglo `[1,3,2,5,7]` ? Si, porque puedo sumar 2 + 7 o 1+3+5. "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Primero, hago una matriz de `suma` columnas y n filas (siendo n la longitud del arreglo) donde: \n",
"\n",
"* La fila i representa al arreglo desde 0 hasta i.\n",
"\n",
"* La columna j representa al número j, que es la suma a la que queremos llegar\n",
"\n",
"\n",
"\n",
"| Arreglo | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |\n",
"|-------------|---|---|---|---|---|---|---|---|---|---|\n",
"| [ ] | \n",
"| [1] | \n",
"| [1,3] | \n",
"| [1,3,2] | \n",
"| [1,3,2,5] | \n",
"| [1,3,2,5,7] | \n",
"\n",
"Esta matriz la poblaremos de Verdaderos o Falsos, dependiendo de si el arreglo de la fila puede sumar el número de la columna. Para esto, diseñamos nuestra ecuación de recurrencia. Notamos:\n",
"\n",
"* Los valores iniciales son los de la primera fila, que es el arreglo vacío. Un arreglo vacío suma 0\n",
"\n",
"* La ecuación de recurrencia consiste en:\n",
"\n",
" * Si el arreglo anterior podía sumar hasta `suma` el arreglo actual también puede. (Como `[1,3]` puede sumar 3, `[1,3,2]` también)\n",
" * Si el arreglo anterior podía sumar hasta `suma` menos el último valor del arreglo actual, entonces el arreglo actual puede sumar hasta `suma`. (`[1,3,2]` puede sumar 5, ya que `[1,3]` puede sumar 5-2)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Valores iniciales**\n",
"\n",
"\\begin{equation}\n",
" DP[0,j]=\\begin{cases}\n",
" True & \\text{if j == 0}. \\\\\n",
" False & \\text{if j != 0}. \\\\\n",
"\\end{cases}\n",
"\\end{equation}\n",
"\n",
"**Relación de recurrencia**\n",
"\n",
"\\begin{equation}\n",
" DP[i,j]=\\begin{cases}\n",
" True & \\text{if DP[i-1,j] is True}. \\\\\n",
" True & \\text{if DP[i-1][j-arr[i-1]] is True}. \\\\\n",
" False & \\text{else}.\n",
"\\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Eventualmente, nos quedara la siguiente matriz:\n",
"\n",
"| Arreglo | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |\n",
"|-------------|---|---|---|---|---|---|---|---|---|---|\n",
"| [ ] | T | F | F | F | F | F | F | F | F | F |\n",
"| [1] | T | T | F | F | F | F | F | F | F | F |\n",
"| [1,3] | T | T | F | T | T | F | F | F | F | F |\n",
"| [1,3,2] | T | T | T | T | T | T | T | F | F | F |\n",
"| [1,3,2,5] | T | T | T | T | T | T | T | T | T | T |\n",
"| [1,3,2,5,7] | T | T | T | T | T | T | T | T | T | T |\n",
"\n",
"Y finalmente, devolvemos lo pedido. Analogamente a cuando devolviamos el último valor de nuestra lista (`DP[n]`), ahora devolvemos el valor de abajo a la derecha de nuestra matriz, es decir, `DP[l,n]`. En este ejemplo, verdadero."
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[True False False False False False False False False False]\n",
" [True True False False False False False False False False]\n",
" [True True False True True False False False False False]\n",
" [True True True True True True True False False False]\n",
" [True True True True True True True True True True]\n",
" [True True True True True True True True True True]]\n"
]
},
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import numpy\n",
"\n",
"def subset_sum(arr, suma):\n",
" cant_columnas = suma + 1\n",
" cant_filas = len(arr) + 1 \n",
" dp = numpy.array( [ [None] *cant_columnas ] * cant_filas )\n",
" \n",
" dp[0,:] = False\n",
" dp[:,0] = True\n",
" \n",
" indices = [(x,y) for x,y in numpy.ndindex(dp.shape) if x is not 0] \n",
" \n",
" for i,j in indices:\n",
" if dp[i-1][j] == True:\n",
" dp[i][j] = True\n",
" elif dp[i-1][j-arr[i-1]] == True:\n",
" dp[i][j] = True\n",
" else:\n",
" dp[i][j] = False\n",
" # Todo equivale a: dp[i][j] = dp[i-1][j] or dp[i-1][j-arr[i-1]]\n",
"\n",
" print(dp) \n",
" return dp[-1][-1]\n",
" \n",
"subset_sum([1,3,2,5,7],9)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Complejidad: $O(\\text{elementos en matriz})== O(n * suma)$** \n",
"\n",
"Cuando una complejidad polinómica depende del *valor* de la entrada se dice que tiene una complejidad pseudo-polinómica.\n",
"\n",
"Esto es en contraste a cuando se depende de la *longitud* de la entrada, por ejemplo cuando se recibe un arreglo de n elementos y se depende de n, sin importar del valor de esos elementos.\n",
"\n",
"Así que el **algoritmo** tiene complejidad **pseudo-polinomial**.\n",
"\n",
"También, este **problema** es **NP-Completo** (tanto NP como NP-Hard), ya que su verificación puede hacerse en tiempo polinómico pero no su resolución (NP) y porque se puede demostrar que todos los problema NP pueden ser reducidos a este (NP-Hard).\n",
"\n",
"Un problema NP-completo con un algoritmo pseudo-polinómico se considera un problema **debilmente NP-completo**."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Problema 7: Longest Common Subsequence [CLRS 15.4]\n",
"\n",
"> Dadas dos secuencias de caracteres (cadenas), encontrar el largo de la máxima subsecuencia en común entre ellas. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, en ambas cadenas **no necesariamente contigua**.\n",
"\n",
"Ej: Por ejemplo, entre las cadenas \"ABC\" y \"CAC\", existen las subsecuencias en comun \"A\", \"C\" y \"AC\". Por ende, el resultado debe ser 2, la longitud de \"AC\".\n",
"\n",
"Ej2: \"AEDFH\" y \"ABCDGH\" debe devolver 3, la longitud de \"ADH\".\n",
"\n",
"**Ojo:** revisar y entender los ejemplos dado; la definición de subsecuencia no es nada intuitiva."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Hago una matriz donde se tenga por filas a una cadena y por columnas a otra.\n",
"\n",
"* La columna j representa a la primera cadena, hasta el caracter j\n",
"\n",
"* La fila i representa a la segunda cadena, hasta el caracter i\n",
"\n",
"| | \"\" | \"A\" | \"AE\" | \"AED\" | \"AEDF\" | \"AEDFH\"|\n",
"|-------------|---|---|---|---|---|---|\n",
"| \"\" | \n",
"| \"A\" | \n",
"| \"AB\" | \n",
"| \"ABC\" | \n",
"| \"ABCD\" | \n",
"| \"ABCDG\" | \n",
"| \"ABCDGH\" | \n",
"\n",
"El valor en la posición i,j será la longitud de la máxima subsecuencia entre las cadenas en la fila i y la columna j."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Valores iniciales**\n",
"\n",
"\\begin{equation}\n",
" DP[i,0]=0\\\\\n",
" DP[0,j]=0\n",
"\\end{equation}\n",
"\n",
"**Relación de recurrencia**\n",
"\n",
"\\begin{equation}\n",
" DP[i,j]=\\begin{cases}\n",
" 1+DP[i-1,j-1] & \\text{if coinciden los últimos caracteres de ambas cadenas}. \\\\\n",
" max( DP[i-1][j] , DP[i][j-1] ) & \\text{else}.\n",
"\\end{cases}\n",
"\\end{equation}"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[0 0 0 0 0 0]\n",
" [0 1 1 1 1 1]\n",
" [0 1 1 1 1 1]\n",
" [0 1 1 1 1 1]\n",
" [0 1 1 2 2 2]\n",
" [0 1 1 2 2 2]\n",
" [0 1 1 2 2 3]]\n"
]
},
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import numpy\n",
"\n",
"def LCS(string1, string2):\n",
" columnas = len(string1) +1\n",
" filas = len(string2) +1\n",
" dp = numpy.array( [ [None] *columnas ] * filas )\n",
" \n",
" dp[0,:] = 0\n",
" dp[:,0] = 0\n",
" \n",
" indices = [(x,y) for x,y in numpy.ndindex(dp.shape) if x is not 0 and y is not 0] \n",
" \n",
" for i,j in indices:\n",
" if string1[:j][-1] == string2[:i][-1]:\n",
" dp[i][j] = 1 + dp[i-1][j-1]\n",
" else:\n",
" dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
"\n",
" print(dp) \n",
" return dp[-1][-1]\n",
" \n",
"LCS(\"AEDFH\",\"ABCDGH\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Complejidad: $O(\\text{longitud de ambas cadenas})== O(n * m)$** "
]
}
],
"metadata": {
"celltoolbar": "Slideshow",
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": false,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment