Escritura de algoritmos dinámicos

6.1 Pasos básicos en el desarrollo de algoritmos dinámicos.

Pasos básicos en el desarrollo de algoritmos dinámicos

1. Definición de subproblemas:

Divide el problema en subproblemas más pequeños que pueden resolverse de forma independiente. Estos subproblemas deben ser superpuestos para que se puedan usar los resultados de cálculos previos.

2. Identificación de estados:

Define todos los posibles estados que pueden surgir al resolver el problema. Los estados deben describir toda la información necesaria para pasar de un paso a otro.

3. Formulación de la relación de recurrencia:

Determina cómo la solución del problema para el estado actual depende de las soluciones para estados anteriores. Esta relación debe expresar cómo se puede obtener la solución óptima, utilizando soluciones para los subproblemas.

4. Definición de casos base:

Define los casos base para los cuales la solución del problema es conocida directamente sin necesidad de más cálculos.

5. Relleno de la tabla:

Crea una tabla (normalmente un array o matriz) para almacenar las soluciones de todos los subproblemas. Usa la relación de recurrencia y los casos base para llenar la tabla de abajo hacia arriba o de arriba hacia abajo.

6. Optimización (memoización):

Si estás usando un enfoque recursivo, añade memoización para guardar resultados de los subproblemas y evitar cálculos repetidos.

Complejidad temporal y espacial de los algoritmos dinámicos

Complejidad temporal:

• La complejidad temporal de los algoritmos dinámicos se suele expresar en términos de la cantidad de subproblemas y el tiempo necesario para calcular cada subproblema.
• En la mayoría de los casos, la complejidad temporal es O(n) o O(n^2), donde n es el tamaño de los datos de entrada.

Complejidad espacial:

• La complejidad espacial depende de la cantidad de estados que es necesario almacenar.
• En algunos casos, es posible reducir la complejidad espacial con optimizaciones, como reducir la memoria utilizada a O(n) o O(1).

6.2 El problema de la mochila.

El problema de la mochila es un problema clásico de optimización combinatoria, que aparece en diversas áreas, incluyendo informática, economía y gestión logística. El objetivo principal del problema es utilizar de manera más eficiente los recursos limitados.

Descripción del problema de la mochila

Hay una mochila que puede soportar un peso específico W. También hay n artículos, cada uno con un peso específico wt[i] y un valor val[i]. Debes determinar qué artículos elegir para maximizar el valor total de los artículos en la mochila, sin exceder su capacidad de peso.

Tipos de problema de la mochila

1. Problema de la mochila 0/1 (0/1 Knapsack Problem):

Cada artículo se puede tomar o no tomar (no se puede tomar parcialmente).

2. Problema de la mochila fraccionaria (Fractional Knapsack Problem):

Cada artículo se puede dividir y tomar cualquier parte de él.

3. Problema de la mochila múltiple (Multiple Knapsack Problem):

Se tienen varias mochilas con diferentes limitaciones de peso.

Formulación del problema de la mochila 0/1 en términos de teoría de algoritmos:

Relación de recurrencia:

Para cada artículo i y para cada peso posible w (de 0 a W), la solución óptima se puede expresar de la siguiente manera:

• Si el artículo i no se incluye en la mochila, entonces el valor óptimo es el valor óptimo para los i − 1 artículos y el peso w.
• Si el artículo i se incluye en la mochila, entonces el valor óptimo es el valor de ese artículo más el valor óptimo para los i − 1 artículos y el peso w − wt[i].

Complejidad temporal y espacial

Complejidad temporal:

La complejidad temporal de este algoritmo es O(nW) donde n es la cantidad de artículos y W es la capacidad de la mochila. Esto se debe a que es necesario rellenar una tabla de tamaño n × W.

Complejidad espacial:

La complejidad espacial también es O(nW), ya que se requiere una tabla para almacenar los resultados intermedios.

Ejemplos de implementación del problema de la mochila 0/1

def knapsack(W, wt, val, n):
    # Creamos una tabla para almacenar valores intermedios
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # Rellenamos la tabla dp de abajo hacia arriba
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# Ejemplo de uso
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Valor máximo de la mochila: {knapsack(W, wt, val, n)}")
        

6.3 El problema del cambio de monedas.

El problema del cambio de monedas es un problema clásico de programación dinámica, que consiste en encontrar el número mínimo de monedas o la cantidad de formas de hacer una cantidad específica de dinero a partir de un conjunto de monedas con valores nominales dados. Este problema tiene dos variantes principales:

Cantidad mínima de monedas (Minimum Coin Change Problem):

Encontrar el número mínimo de monedas que en total sumen la cantidad dada.

Número de formas (Number of Ways to Make Change):

Encontrar la cantidad de formas diferentes de sumar la cantidad dada a partir del conjunto de monedas dado.

Variante 1. Cantidad mínima de monedas

Formulación del problema

Dado:

• Un número ilimitado de monedas con valores nominales específicos.
• Una cantidad objetivo S.

Necesitas:

• Encontrar el número mínimo de monedas que sumen S.

Solución usando programación dinámica

Relación de recurrencia:

• Sea dp[i] el número mínimo de monedas necesario para hacer la cantidad i.
• Para cada moneda c del conjunto de monedas, si i ≥ c, entonces: dp[i] = min(dp[i], dp[i − c] + 1).

Casos base:

• dp[0] = 0 (para la cantidad 0 se requieren 0 monedas).

Complejidad temporal y espacial:

• Complejidad temporal: O(n ⋅ S), donde n es el número de denominaciones de monedas, S es la cantidad objetivo.
• Complejidad espacial: O(S), ya que se requiere un array para almacenar el número mínimo de monedas para cada cantidad de 0 a S.

Ejemplo de implementación en Python

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# Ejemplo de uso
coins = [1, 2, 5]
S = 11
print(f"Cantidad mínima de monedas para la cantidad {S}: {min_coins(coins, S)}")
        
        

El problema del cambio de monedas demuestra la flexibilidad de la programación dinámica. Se utiliza para la enseñanza y el estudio de técnicas algorítmicas, ya que muestra cómo se pueden usar relaciones de recurrencia y casos base para resolver problemas de manera eficiente.