Problema de la mochila (Knapsack)

Conocimientos previos: Introducción a la Programación Dinámica 

Introducción

Consideremos el siguiente ejemplo:

[USACO07 Dec] Charm Bracelet 

Hay $n$ ítems distintos y una mochila (knapsack) de capacidad $W$. Cada ítem tiene 2 atributos: peso ($w_{i}$) y valor ($v_{i}$). Hay que seleccionar un subconjunto de ítems para poner en la mochila de modo que el peso total no exceda la capacidad $W$ y el valor total se maximice.

En el ejemplo anterior, cada objeto tiene solo dos estados posibles (tomado o no tomado), que corresponden al binario 0 y 1. Por eso este tipo de problema se llama “problema de la mochila 0-1” (0-1 knapsack).

Mochila 0-1 (0-1 Knapsack)

Explicación

En el ejemplo anterior, la entrada del problema es la siguiente: el peso del $i^{th}$ ítem $w_{i}$, el valor del $i^{th}$ ítem $v_{i}$, y la capacidad total de la mochila $W$.

Sea $f_{i, j}$ el estado de programación dinámica que guarda el valor total máximo que la mochila puede llevar con capacidad $j$, cuando solo se consideran los primeros $i$ ítems.

Suponiendo que ya se procesaron todos los estados de los primeros $i-1$ ítems, ¿cuáles son las opciones para el $i^{th}$ ítem?

• Cuando no se pone en la mochila, la capacidad restante no cambia y el valor total tampoco. Por lo tanto, el valor máximo en este caso es $f_{i-1, j}$
• Cuando se pone en la mochila, la capacidad restante disminuye en $w_{i}$ y el valor total aumenta en $v_{i}$, así que el valor máximo en este caso es $f_{i-1, j-w_i} + v_i$

De aquí podemos derivar la ecuación de transición de la DP:

$$f_{i, j} = \max(f_{i-1, j}, f_{i-1, j-w_i} + v_i)$$

Además, como $f_{i}$ solo depende de $f_{i-1}$, podemos eliminar la primera dimensión. Obtenemos la regla de transición

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

que debe ejecutarse en orden decreciente de $j$ (de modo que $f_{j-w_i}$ corresponda implícitamente a $f_{i-1,j-w_i}$ y no a $f_{i,j-w_i}$).

Es importante entender esta regla de transición, porque la mayoría de las transiciones de los problemas de mochila se derivan de forma similar.

Implementación

El algoritmo descrito se puede implementar en $O(nW)$ así:

for (int i = 1; i <= n; i++)
  for (int j = W; j >= w[i]; j--)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

De nuevo, nótese el orden de ejecución. Debe seguirse estrictamente para garantizar el siguiente invariante: justo antes de procesar el par $(i, j)$, $f_k$ corresponde a $f_{i,k}$ para $k > j$, pero a $f_{i-1,k}$ para $k < j$. Esto asegura que $f_{j-w_i}$ se toma del paso $(i-1)$-ésimo, y no del $i$-ésimo.

Mochila completa (Complete Knapsack)

El modelo de mochila completa es similar a la mochila 0-1; la única diferencia es que un ítem se puede seleccionar un número ilimitado de veces en lugar de solo una.

Podemos retomar la idea de la mochila 0-1 para definir el estado: $f_{i, j}$, el valor máximo que la mochila puede obtener usando los primeros $i$ ítems con capacidad máxima $j$.

Cabe señalar que, aunque la definición del estado es similar a la de la mochila 0-1, su regla de transición es distinta.

Explicación

El enfoque trivial es, para los primeros $i$ ítems, enumerar cuántas veces se toma cada ítem. La complejidad temporal de esto es $O(n^2W)$.

Esto produce la siguiente ecuación de transición:

$$f_{i, j} = \max\limits_{k=0}^{\infty}(f_{i-1, j-k\cdot w_i} + k\cdot v_i)$$

Al mismo tiempo, se simplifica en una ecuación “plana”:

$$f_{i, j} = \max(f_{i-1, j},f_{i, j-w_i} + v_i)$$

La razón por la que esto funciona es que $f_{i, j-w_i}$ ya fue actualizado por $f_{i, j-2\cdot w_i}$ y así sucesivamente.

Al igual que en la mochila 0-1, podemos eliminar la primera dimensión para optimizar la complejidad espacial. Esto nos da la misma regla de transición que la mochila 0-1.

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

Implementación

El algoritmo descrito se puede implementar en $O(nW)$ así:

for (int i = 1; i <= n; i++)
  for (int j = w[i]; j <= W; j++)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

A pesar de tener la misma regla de transición, el código anterior es incorrecto para la mochila 0-1.

Observando el código con cuidado, vemos que para el ítem $i$ que se está procesando y el estado actual $f_{i,j}$, cuando $j\geqslant w_{i}$, $f_{i,j}$ se verá afectado por $f_{i,j-w_{i}}$. Esto equivale a poder poner el ítem $i$ en la mochila varias veces, lo cual es coherente con el problema de la mochila completa y no con el de la mochila 0-1.

Mochila múltiple (Multiple Knapsack)

La mochila múltiple también es una variante de la mochila 0-1. La diferencia principal es que hay $k_i$ unidades de cada ítem en lugar de solo $1$.

Explicación

Una idea muy simple es: “elegir cada ítem $k_i$ veces” equivale a “se seleccionan $k_i$ copias del mismo ítem una por una”. Así se convierte en un modelo de mochila 0-1, que se puede describir con la función de transición:

$$f_{i, j} = \max_{k=0}^{k_i}(f_{i-1,j-k\cdot w_i} + k\cdot v_i)$$

La complejidad temporal de este proceso es $O(W\sum\limits_{i=1}^{n}k_i)$

Optimización por agrupamiento binario

Seguimos considerando convertir el modelo de mochila múltiple en un modelo de mochila 0-1 para optimizarlo. La complejidad temporal $O(Wn)$ no se puede optimizar más con el enfoque anterior, así que nos concentramos en el componente $O(\sum k_i)$.

Sea $A_{i, j}$ el $j^{th}$ ítem obtenido al partir el $i^{th}$ ítem. En el enfoque trivial discutido arriba, $A_{i, j}$ representa el mismo ítem para todo $j \leq k_i$. La razón principal de nuestra baja eficiencia es que hacemos mucho trabajo repetitivo. Por ejemplo, considerar seleccionar ${A_{i, 1},A_{i, 2}}$ y seleccionar ${A_{i, 2}, A_{i, 3}}$. Estas dos situaciones son completamente equivalentes. Por lo tanto, optimizar el método de partición reducirá mucho la complejidad temporal.

El agrupamiento se vuelve más eficiente usando agrupamiento binario.

En concreto, $A_{i, j}$ contiene $2^j$ ítems individuales ($j\in[0,\lfloor \log_2(k_i+1)\rfloor-1]$). Si $k_i + 1$ no es una potencia entera de $2$, se usa otro paquete de tamaño $k_i-(2^{\lfloor \log_2(k_i+1)\rfloor}-1)$ para completar.

Con el método de partición anterior, es posible obtener cualquier suma de $\leq k_i$ ítems seleccionando algunos $A_{i, j}$. Tras partir cada ítem de la forma descrita, basta usar el método de mochila 0-1 para resolver la nueva formulación del problema.

Esta optimización nos da una complejidad temporal de $O(W\sum\limits_{i=1}^{n}\log k_i)$.

Implementación

index = 0;
for (int i = 1; i <= n; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

Optimización con cola monótona

En esta optimización, el objetivo es convertir el problema de la mochila en uno de cola de máximos .

Por conveniencia de la descripción, sea $g_{x, y} = f_{i, x \cdot w_i + y} ,\space g’${x, y} = f{i-1, x \cdot w_i + y}. Entonces la regla de transición se puede escribir como:

$$g_{x, y} = \max_{k=0}^{k_i}(g’_{x-k, y} + v_i \cdot k)$$

Además, sea $G_{x, y} = g’_{x, y} - v_i \cdot x$. Entonces la regla de transición se puede expresar como:

$$g_{x, y} \gets \max_{k=0}^{k_i}(G_{x-k, y}) + v_i \cdot x$$

Esto se transforma en una forma clásica de optimización con cola monótona. $G_{x, y}$ se puede calcular en $O(1)$, así que para un $y$ fijo podemos calcular $g_{x, y}$ en tiempo $O(\lfloor \frac{W}{w_i} \rfloor)$. Por lo tanto, la complejidad de hallar todos los $g_{x, y}$ es $O(\lfloor \frac{W}{w_i} \rfloor) \times O(w_i) = O(W)$. De este modo, la complejidad total del algoritmo se reduce a $O(nW)$.

Mochila mixta (Mixed Knapsack)

El problema de la mochila mixta combina los tres problemas descritos arriba. Es decir, algunos ítems solo se pueden tomar una vez, algunos se pueden tomar infinitas veces, y algunos se pueden tomar a lo sumo $k$ veces.

El problema puede parecer intimidante, pero mientras se entiendan las ideas centrales de los problemas de mochila anteriores y se combinen, se puede resolver. El pseudocódigo de la solución es:

for (each item) {
  if (0-1 knapsack)
    Apply 0-1 knapsack code;
  else if (complete knapsack)
    Apply complete knapsack code;
  else if (multiple knapsack)
    Apply multiple knapsack code;
}

Problemas para practicar

• Atcoder: Knapsack-1 
• Atcoder: Knapsack-2 
• LeetCode - 494. Target Sum 
• LeetCode - 416. Partition Equal Subset Sum 
• LeetCode - 474. Ones and Zeroes 
• CSES: Book Shop II 
• DMOJ: Knapsack-3 
• DMOJ: Knapsack-4