El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

La programación dinámica es una técnica de diseño de algoritmos que se utiliza para resolver problemas complejos dividiéndolos en subproblemas más simples y almacenando los resultados de estos subproblemas para evitar cálculos redundantes. Esta técnica es especialmente útil para problemas de optimización y se basa en dos principios fundamentales: subestructura óptima y superposición de subproblemas.

Conceptos Clave

Subestructura Óptima

Un problema exhibe subestructura óptima si una solución óptima del problema puede construirse eficientemente a partir de soluciones óptimas de sus subproblemas.

Superposición de Subproblemas

Un problema exhibe superposición de subproblemas si los subproblemas se repiten muchas veces. En lugar de resolver los mismos subproblemas una y otra vez, la programación dinámica almacena los resultados de los subproblemas en una tabla (usualmente un array o matriz) para reutilizarlos.

Pasos para Diseñar un Algoritmo de Programación Dinámica

Definir la estructura de la solución óptima.
Definir recursivamente el valor de una solución óptima.
Calcular el valor de una solución óptima de manera ascendente (bottom-up).
Construir una solución óptima a partir de los valores calculados.

Ejemplo Práctico: Problema de la Mochila (Knapsack Problem)

Descripción del Problema

Dado un conjunto de elementos, cada uno con un peso y un valor, determinar el número de cada elemento que se puede incluir en una colección para que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible.

Formulación del Problema

Entrada:
- n: número de elementos.
- W: capacidad máxima de la mochila.
- weights[]: array de pesos de los elementos.
- values[]: array de valores de los elementos.
Salida:
- Valor máximo que se puede obtener con una capacidad de mochila W.

Solución con Programación Dinámica

Paso 1: Definir la Estructura de la Solución Óptima

Definimos dp[i][w] como el valor máximo que se puede obtener usando los primeros i elementos con una capacidad de mochila w.

Paso 2: Definir Recursivamente el Valor de una Solución Óptima

La relación de recurrencia es: \[ dp[i][w] = \max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]) \]

Si no incluimos el i-ésimo elemento, el valor es dp[i-1][w].
Si incluimos el i-ésimo elemento, el valor es dp[i-1][w - weights[i-1]] + values[i-1].

Paso 3: Calcular el Valor de una Solución Óptima de Manera Ascendente

def knapsack(values, weights, W):
    n = len(values)
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

# Ejemplo de uso
values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
print(knapsack(values, weights, W))  # Output: 220

Paso 4: Construir una Solución Óptima a partir de los Valores Calculados

Para reconstruir la solución óptima, podemos rastrear los elementos incluidos en la mochila:

def knapsack_solution(values, weights, W):
    n = len(values)
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    # Reconstruir la solución óptima
    w = W
    items_selected = []
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            items_selected.append(i-1)
            w -= weights[i-1]
    
    return dp[n][W], items_selected

# Ejemplo de uso
values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
max_value, items_selected = knapsack_solution(values, weights, W)
print(f"Valor máximo: {max_value}")  # Output: 220
print(f"Elementos seleccionados: {items_selected}")  # Output: [2, 1]

Ejercicios Prácticos

Ejercicio 1: Problema de la Suma de Subconjuntos

Dado un conjunto de números enteros y un número sum, determinar si hay un subconjunto del conjunto dado con una suma igual a sum.

Ejercicio 2: Problema de la Secuencia Común Más Larga (LCS)

Dadas dos secuencias, encontrar la longitud de la subsecuencia común más larga.

Ejercicio 3: Problema de la Cadena de Matrices

Dada una secuencia de matrices, encontrar la manera más eficiente de multiplicarlas.

Soluciones a los Ejercicios

Solución al Ejercicio 1

def subset_sum(nums, sum):
    n = len(nums)
    dp = [[False for _ in range(sum + 1)] for _ in range(n + 1)]
    
    for i in range(n + 1):
        dp[i][0] = True
    
    for i in range(1, n + 1):
        for j in range(1, sum + 1):
            if nums[i-1] <= j:
                dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i-1]]
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[n][sum]

# Ejemplo de uso
nums = [3, 34, 4, 12, 5, 2]
sum = 9
print(subset_sum(nums, sum))  # Output: True

Solución al Ejercicio 2

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

# Ejemplo de uso
X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y))  # Output: 4

Solución al Ejercicio 3

def matrix_chain_order(p):
    n = len(p) - 1
    dp = [[0 for _ in range(n)] for _ in range(n)]
    
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                q = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
                if q < dp[i][j]:
                    dp[i][j] = q
    
    return dp[0][n-1]

# Ejemplo de uso
p = [1, 2, 3, 4]
print(matrix_chain_order(p))  # Output: 18

Conclusión

La programación dinámica es una técnica poderosa para resolver problemas de optimización que involucran subproblemas superpuestos y subestructura óptima. Al almacenar los resultados de los subproblemas, podemos mejorar significativamente la eficiencia de nuestros algoritmos. En este módulo, hemos cubierto los conceptos clave, la metodología para diseñar algoritmos de programación dinámica y hemos trabajado con ejemplos prácticos y ejercicios para reforzar el aprendizaje.

Programación Dinámica