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.

🔗 Relacionados