Problema 52: Transporte de materiales de investigación

Este problema representa una versión clásica del problema de la mochila completa, donde cada elemento puede seleccionarse múltiples veces. A diferencia del problema de mochila 0-1, en el que cada ítem solo se puede usar una vez y el bucle interno debe recorrerse en orden inverso para evitar reutilizaciones, en este caso el recorrido se realiza en orden ascendente para permitir selecciones repetidas.

La clave está en cómo se estructura la transición del estado. Sea dp[j] el valor máximo que se puede obtener con una capacidad de mochila igual a j. Para cada ítem con peso w[i] y valor v[i], actualizamos:

dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

El orden del bucle es fundamental: primero iteramos sobre los ítems y luego sobre las capacidades desde w[i] hasta la capacidad total. Esto garantiza que al procesar una capacidad mayor, ya se haya considerado la posibilidad de incluir múltiples copias del mismo ítem.

Alternativamente, también es válido invertir el orden de los ciclos (primero capacidad, luego ítems), lo cual también produce resultados correctos en el caso de mochila completa debido a la naturaleza acumulativa del problema.

Problema 518: Cambio de monedas II

Dado un conjunto de denominaciones y una cantidad objetivo, se requiere calcular cuántas combinaciones distintas existen para formar esa cantidad. Este es un problema típico de conteo de combinaciones usando programación dinámica.

Definimos dp[j] como el número de formas de sumar exactamente j usando las monedas disponibles. La inicialización establece dp[0] = 1, ya que hay una única forma de formar suma cero: no usar ninguna moneda.

La transición se realiza mediante:

dp[j] += dp[j - coin];

Es crucial mantener el orden: primero iterar sobre las monedas y luego sobre las cantidades desde coin hasta amount. Este orden evita contar permutaciones diferentes como combinaciones únicas; es decir, asegura que [1,2] y [2,1] no se cuenten por separado, tratándose como la misma combinación.

Problema 377: Suma de combinaciones IV

A diferencia del problema anterior, aquí sí importa el orden de los elementos. Por ejemplo, [1,2] y [2,1] se consideran secuencias distintas. Este cambio transforma el problema de conteo de combinaciones en uno de conteo de permutaciones.

Para lograr esto, se invierte el orden de los bucles: ahora se itera primero sobre la suma objetivo (de 1 a target) y luego sobre los números disponibles. De esta forma, en cada paso se permite insertar cualquier número siempre que sea posible, generando todas las posibles secuencias ordenadas.

La lógica detrás de esta inversión es que, al fijar una suma intermedia i, exploramos todas las posibilidades de llegar a ella desde i - num, independientemente del orden en que se hayan construido esos estados preevios.

Además, se incluye una verificación contra desbordamiento entero antes de actualizar:

if (i >= num && dp[i] < INT_MAX - dp[i - num]) {
    dp[i] += dp[i - num];
}

Problema 70: Subir escaleras

Este problema clásico puede reinterpretarse como una instancia del problema de la mochila completa. Cada paso puede verse como un "ítem" de tamaño variable (1, 2, ..., m). El objetivo es contar cuántas maneras distintas existen de alcanzar el escalón n, permitiendo saltos de hasta m peldaños.

Sea dp[i] el número total de formas de llegar al escalón i. Para cada posición, se consideran todos los tamaños de salto posibles j (desde 1 hasta m). Si i >= j, entonces:

dp[i] += dp[i - j];

Nuevamente, el bucle externo recorre los escalones (la "mochila") y el interno los tipos de pasos ("ítems"), lo cual permite generar todas las secuencias posibles de movimientos, análogo al problema 377.