Mochila ilimitada y Coin Change II

En la mochila ilimitada, cada ítem se puede seleccionar cualquier número de veces (a diferencia de la mochila 0/1, donde cada ítem se utiliza como máximo una vez). La definición del estado es la misma: dp[c] = valor máximo alcanzable con capacidad c; sin embargo, cambia la dirección de la iteración. Como los ítems se pueden reutilizar, al actualizar dp[c] queremos permitir que el ítem actual se vuelva a utilizar, por lo que iteramos sobre la capacidad de izquierda a derecha (hacia delante).

Recuerde que en la mochila 0/1 iterábamos de derecha a izquierda para impedir la reutilización. En la mochila ilimitada hacemos lo contrario: iteramos de izquierda a derecha. Al calcular dp[c], dp[c-w] ya se ha actualizado en el paso actual; esto significa que el ítem i posiblemente ya se incluyó. Eso es exactamente lo que queremos: el ítem i se puede añadir de nuevo a una solución que ya contiene el ítem i.

Coin Change II plantea lo siguiente: dadas las denominaciones de unas monedas y un importe, cuente el número de formas distintas de alcanzar dicho importe (cada moneda se puede utilizar un número ilimitado de veces). Se trata de una variante de la mochila ilimitada en la que, en lugar de maximizar el valor, contamos combinaciones. Defina dp[c] como el número de formas de obtener el importe c. Caso base: dp[0] = 1 (hay una forma de obtener 0: no seleccionar nada).

Para cada moneda, itere sobre los importes de izquierda a derecha y acumule: dp[c] += dp[c - coin]. El caso base dp[0] = 1 inicializa el recuento. Observe que el bucle externo recorre las monedas y el interno recorre los importes; esto produce de forma natural recuentos de combinaciones (no permutaciones), porque cada denominación de moneda se considera exactamente una vez en cada pasada externa.

El orden de los bucles es de vital importancia. Si colocamos el importe en el bucle externo y la moneda en el interno, contamos permutaciones (el orden importa). Para amount=5 con coins [1,2], 1+2+2 y 2+1+2 se cuentan por separado. Si colocamos la moneda en el bucle externo, contamos combinaciones (el orden no importa): 1+2+2 y 2+1+2 son lo mismo. Coin Change II solicita combinaciones, por lo que la moneda debe estar en el bucle externo.

Otro problema clásico de mochila ilimitada: dada una varilla de longitud n y los precios de cada longitud de varilla entre 1 y n, encuentre el ingreso máximo cortando la varilla de forma óptima. Cada pieza de longitud l se puede vender por price[l], y las piezas se pueden reutilizar (la varilla se puede cortar en varias piezas de la misma longitud). Esto se corresponde directamente con la mochila ilimitada, con W = n y los distintos tamaños de corte como ítems.

Coin Change I (un problema diferente) solicita el número mínimo de monedas necesario para obtener un importe objetivo. Aquí dp[c] = número mínimo de monedas para obtener el importe c. Recurrencia: dp[c] = min(dp[c], dp[c - coin] + 1). Inicialice todas las entradas con inf, excepto dp[0] = 0. Este problema también es ilimitado (las monedas se pueden reutilizar), por lo que se debe iterar de izquierda a derecha. Devuelva dp[amount] si es finito; de lo contrario, -1.

Las tres variantes de mochila ilimitada utilizan operaciones diferentes sobre dp[c-coin]: Maximizar el valor: dp[c] = max(dp[c], dp[c-w] + v); inicializar con 0. Minimizar el coste: dp[c] = min(dp[c], dp[c-coin] + 1); inicializar con inf, dp[0]=0. Contar formas: dp[c] += dp[c-coin]; inicializar con 0, dp[0]=1. Reconocer qué variante corresponde es la mitad del trabajo en los problemas de entrevistas.

Todas las variantes de mochila ilimitada se ejecutan en tiempo O(n × W) y espacio O(W), donde n es el número de tipos de ítems y W es el importe objetivo. En los problemas de monedas, n es el número de denominaciones. En las entrevistas, indique la variante (máximo/mínimo/recuento), escriba la programación dinámica 1D y especifique claramente si el bucle externo recorre las monedas o el importe; los evaluadores saben que esta distinción pone a prueba una comprensión profunda de la programación dinámica.

Utilice estas señales para identificar qué variante corresponde: reutilización ilimitada → ilimitada (iteración hacia delante); cada ítem exactamente una vez → 0/1 (iteración hacia atrás); si el problema indica «cualquier número de veces», «suministro infinito» o «se permite reutilizar» → ilimitada. Ejemplos: cambio de monedas, corte de varillas y separación de enteros; todos son problemas ilimitados. Subset sum, partition y mochila 0/1 son problemas 0/1. Equivocarse en esto provoca respuestas incorrectas difíciles de depurar.

Integer Break (LeetCode 343): divida un entero n en al menos 2 enteros positivos para maximizar su producto. Se trata de una mochila ilimitada en la que los «ítems» son los enteros del 2 al n-1. Defina dp[i] = producto máximo de enteros cuya suma es i. Para cada ítem j entre 2 e i, dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Esto muestra cómo el patrón de la mochila ilimitada se generaliza más allá del contexto de las monedas.

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección ha aprendido: la mochila ilimitada itera sobre la capacidad de izquierda a derecha para permitir la reutilización de los ítems, Coin Change II cuenta combinaciones colocando la moneda en el bucle externo, y las tres variantes —maximizar, minimizar y contar— solo se diferencian en la operación y la inicialización de la programación dinámica. A continuación utilizaremos la mochila 0/1 para resolver Partition Equal Subset Sum.