DP con bitmask
Tema: Programación Dinámica · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 22 de la Ruta de Aprendizaje.
Qué hace
Usa un número entero como conjunto: el bit i dice si el elemento i ya fue usado. Permite hacer DP sobre ‘qué subconjunto llevo’, que es la forma de convertir un O(n!) en O(2^n · n).
Complejidad: O(2^n · n) o O(2^n · n²) según la transición. Cabe hasta n ≈ 20-22.
Cuándo usarlo
Cuando el enunciado da un n sospechosamente chico (≤ 20) y el problema pide asignar, emparejar o recorrer todo en algún orden: asignación de tareas, viajante de comercio, cubrir con piezas. Módulo 22 de la Ruta de Aprendizaje.
Implementación recomendada (C++)
// costo mínimo de asignar n tareas a n personas (persona i toma una tarea libre)
long long asignacion(const vector<vector<int>>& costo) {
int n = costo.size();
vector<long long> dp(1 << n, LLONG_MAX); // dp[masc] = costo de haber asignado masc (long long: suma de n costos)
dp[0] = 0;
for (int masc = 0; masc < (1 << n); masc++) {
if (dp[masc] == LLONG_MAX) continue; // estado inalcanzable
int i = __builtin_popcount(masc); // bits encendidos = persona que toca ahora
if (i == n) continue;
for (int t = 0; t < n; t++)
if (!(masc >> t & 1)) // ¿la tarea t sigue libre?
dp[masc | (1 << t)] = min(dp[masc | (1 << t)], dp[masc] + costo[i][t]);
}
return dp[(1 << n) - 1]; // todas las tareas asignadas
}⚠️ Notas
Los tres idiomas que hay que leer sin pensar: 1 << t es el conjunto que solo tiene a t; masc >> t & 1 pregunta si t está en el conjunto; masc | 1 << t agrega t. __builtin_popcount(masc) cuenta los bits encendidos. Ojo con la memoria: 2^20 enteros son 4 MB, pero 2^20 × n ya son 80 MB. El truco de derivar la persona actual del popcount ahorra una dimensión entera del estado.