La programación dinámica es una técnica poderosa para resolver problemas complejos dividiéndolos en subproblemas más pequeños y manejables. Esta sección se centra en varios tipos de problemas de mochila resueltos mediante DP.

1. Problema de la Mochila 0/1

Este es un problema clásico de optimización. Dada una colección de artículos, cada uno con un peso y un valor, determinamos los artículos a 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. Solo podemos tomar cada artículo una vez (de ahí 0/1).

Definición del Estado y Transiciones

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

• Caso Base: dp[0][w] = 0 para toda w y dp[i][0] = 0 para todo i. Si no hay artículos o la capacidad es cero, el valor máximo es cero.

• Transición: Para cada artículo i y capacidad w, tenemos dos opciones:

  1. No incluir el artículo i: El valor máximo es el mismo que el valor obtenido con los primeros i-1 artículos: dp[i-1][w].
  2. Incluir el artículo i: Esto solo es posible si el peso del artículo i (wt[i-1]) no excede la capacidad actual w. Si lo incluimos, el valor máximo es el valor del artículo i (val[i-1]) más el valor máximo obtenido con los primeros i-1 artículos y la capacidad restante (w - wt[i-1]): val[i-1] + dp[i-1][w - wt[i-1]].

  Tomamos el máximo de estas dos opciones.

Implementación en Java:

int resolverMochila01(int capacidad, int[] pesos, int[] valores) {
    int n = pesos.length;
    // dp[i][w] = valor máximo usando los primeros i artículos con capacidad w
    int[][] dp = new int[n + 1][capacidad + 1];

    // Los casos base (dp[0][w] y dp[i][0]) ya están inicializados a 0 por defecto

    for (int i = 1; i <= n; i++) {
        int pesoActual = pesos[i - 1];
        int valorActual = valores[i - 1];
        for (int w = 1; w <= capacidad; w++) {
            if (w - pesoActual < 0) {
                // No se puede incluir el artículo actual
                dp[i][w] = dp[i - 1][w];
            } else {
                // Elegir entre incluir o no incluir el artículo actual
                dp[i][w] = Math.max(
                    dp[i - 1][w], // No incluir
                    valorActual + dp[i - 1][w - pesoActual] // Incluir
                );
            }
        }
    }
    
    return dp[n][capacidad];
}

2. Problema de la Partición de Subconjuntos (Suma Iguales)

Daddo un array de enteros positivos, determina si se puede dividir el array en dos subconjuntos de igual suma.

Enfoque

Este problema se puede reducir al problema de la mochila 0/1. Primero, calculamos la suma total de todos los elementos en el array. Si la suma total es impar, es imposible dividir el array en dos subconjuntos de igual suma, por lo que devolvemos false. Si la suma total es par, nuestro objetivo es ancontrar un subconjunto cuya suma sea exactamente la mitad de la suma total (sum / 2). Si podemos encontrar tal subconjunto, el resto de los elementos formarán el otro subconjunto con la misma suma.

Definición del Estado y Transiciones

Definimos dp[i][j] como un booleano que indica si es posible obtener una suma j utilizando los primeros i elementos del array.

• Caso Base: dp[i][0] = true para todo i (siempre es posible obtener una suma de 0). dp[0][j] = false para j > 0 (sin elementos, no se puede obtener una suma positiva).

• Transición: Para cada elemento i y suma objetivo j:

  1. No incluir el elemento i: Si es posible obtener la suma j sin el elemento actual, entonces dp[i][j] es true si dp[i-1][j] es true.
  2. Incluir el elemento i: Si el elemento actual (nums[i-1]) no es mayor que la suma objetivo j, y es posible obtener la suma j - nums[i-1] usando los elementos anteriores, entonces dp[i][j] puede ser true.

  dp[i][j] es true si alguna de estas condiciones es true: dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]] (si j >= nums[i-1]).

Implementación en Java:

boolean puedeParticionar(int[] nums) {
    int sumaTotal = 0;
    for (int num : nums) {
        sumaTotal += num;
    }

    if (sumaTotal % 2 != 0) {
        return false; // Suma impar, imposible de particionar
    }

    int sumaObjetivo = sumaTotal / 2;
    int n = nums.length;

    // dp[i][j] = true si se puede obtener la suma j usando los primeros i números
    boolean[][] dp = new boolean[n + 1][sumaObjetivo + 1];

    // Caso base: obtener suma 0 es siempre posible
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    for (int i = 1; i <= n; i++) {
        int numActual = nums[i - 1];
        for (int j = 1; j <= sumaObjetivo; j++) {
            if (j - numActual < 0) {
                // No se puede incluir el número actual
                dp[i][j] = dp[i - 1][j];
            } else {
                // Se puede obtener la suma j si se podía obtener sin el número actual
                // O si se podía obtener la suma j - numActual sin el número actual
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - numActual];
            }
        }
    }
    
    return dp[n][sumaObjetivo];
}

3. Problema de la Mochila Completa (Monedas)

Este es un problema de conteo. Dada una cantidad de dinero y una lista de denominaciones de monedas, determina el número total de combinaciones de monedas que suman exactamente la cantidad dada. Puedes usar cada tipo de moneda un número iliimtado de veces.

Enfoque

Este problema se puede resolver usando DP, similar a la mochila 0/1 pero con una ligera modificación en la transición para permitir el uso ilimitado de artículos (monedas).

Definición del Estado y Transiciones

Definimos dp[i][j] como el número de formas de obtener la suma j usando las primeras i monedas.

• Caso Base: dp[i][0] = 1 para todo i (hay una forma de obtener una suma de 0: no usar ninguna moneda). dp[0][j] = 0 para j > 0.

• Transición: Para cada moneda i y cantidad j:

  1. No usar la moneda i: El número de formas es el mismo que usar las primeras i-1 monedas: dp[i-1][j].
  2. Usar la moneda i: Si la cantidad j es mayor o igual al valor de la moneda actual (coins[i-1]), podemos incluir esta moneda. El número de formas es dp[i][j - coins[i-1]] (notar que usamos dp[i] aquí, no dp[i-1], porque podemos usar la moneda actual múltiples veces).

  dp[i][j] es la suma de las formas de no usar la moneda actual y las formas de usarla (si es posible): dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]] (si j >= coins[i-1]). Si no se puede usar la moneda actual (j < coins[i-1]), entonces dp[i][j] = dp[i-1][j].

Implementación en Java:

int contarCombinacionesMonedas(int cantidad, int[] monedas) {
    int n = monedas.length;
    // dp[i][j] = número de formas de obtener la cantidad j usando las primeras i monedas
    int[][] dp = new int[n + 1][cantidad + 1];

    // Caso base: Hay 1 forma de obtener cantidad 0 (no usar ninguna moneda)
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }

    for (int i = 1; i <= n; i++) {
        int monedaActual = monedas[i - 1];
        for (int j = 1; j <= cantidad; j++) {
            if (j - monedaActual >= 0) {
                // Número de formas = (formas sin usar moneda actual) + (formas usando moneda actual)
                dp[i][j] = dp[i - 1][j] + dp[i][j - monedaActual];
            } else {
                // No se puede usar la moneda actual, hereda el valor de la fila anterior
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    return dp[n][cantidad];
}