La compresión de estados consiste en representar múltiples estados como un único valor, comúnmente mediante bits. En problemas que requieren una progresión secuencial, como la programación dinámica convencional, solo se maneja un estado a la vez, lo que resulta insuficiente para escenarios con estados múltiples. Por ello, se emplea la compresión de estados.
Estos estados se codifican en formato binario. Con \(m\) estados, existen \(2^m\) combinaciones posibles. Por ejemplo, con 4 estados, \(0010\) indica que solo el segundo estado está satisfecho. Se excluye el estado donde ningún bit está activo, por lo que el número total de estados a considerar es \(2^m - 1\). Para fusionar estados, se utiliza el operador OR (\(|\)) que combina los bits activos de dos representaciones.
Problema de los dulces
Un vendedor ofrece \(M\) tipos de sabores de dulces, numerados del 1 al \(M\). Un cliente quiere probar todos los sabores, pero los dulces se venden en paquetes de \(K\) unidades cada uno, sin venta individual. Cada paquete indica los sabores de sus dulces. Dados \(N\) paquetes, se debe caclular el mínimo número de paquetes necesarios para cubrir todos los sabores, o -1 si es imposible.
Formato de entrada: primera línea con \(N\), \(M\) y \(K\); las siguientes \(N\) líneas con \(K\) enteros representando los sabores de cada paquete. Salida: un entero con la respuesta mínima o -1.
Ejemplo de entrada:
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
Salida esperada: 2
La solución implica calcular el bitmask de sabores para cada paquete y luego aplicar DP. La complejidad temporal es \(O(n \times 2^m)\). A continuación, un código de ejemplo en C++:
#include #include using namespace std;
int main() { int num_packages, num_flavors, candies_per_package; cin >> num_packages >> num_flavors >> candies_per_package;
vector<int> packages(num_packages, 0);
for (int i = 0; i < num_packages; ++i) {
for (int j = 0; j < candies_per_package; ++j) {
int flavor;
cin >> flavor;
packages[i] |= (1 << (flavor - 1));
}
}
vector<int> dp(1 << num_flavors, -1);
dp[0] = 0;
for (int i = 0; i < num_packages; ++i) {
int current_package = packages[i];
vector<int> new_dp = dp;
for (int state = 0; state < (1 << num_flavors); ++state) {
if (dp[state] != -1) {
int new_state = state | current_package;
if (new_dp[new_state] == -1 || new_dp[new_state] > dp[state] + 1) {
new_dp[new_state] = dp[state] + 1;
}
}
}
dp = new_dp;
}
int target = (1 << num_flavors) - 1;
if (dp[target] == -1) {
cout << -1 << endl;
} else {
cout << dp[target] << endl;
}
return 0;
}
</div>### Problema del ratón y el queso
Otro ejemplo común es el problema donde un ratón debe comer todos los quesos ubicados en un plano. Se modela cada queso como un bit en una máscara: 0 si no ha sido comido, 1 si ya se comió. La DP \\(dp\[mask\]\[last\]\\) almacena la distancia mínima para comer los quesos representados por \\(mask\\), terminando en el queso \\(last\\). Se calculan distancias entre todos los puntos y se actualizan los estados usando bitmask.
<div>```
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const double INF = 1e18;
double distance_calculate(double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main() {
int cheese_count;
cin >> cheese_count;
vector<double> x_coords(cheese_count + 1), y_coords(cheese_count + 1);
for (int i = 1; i <= cheese_count; ++i) {
cin >> x_coords[i] >> y_coords[i];
}
x_coords[0] = 0.0;
y_coords[0] = 0.0;
vector<vector<double>> distances(cheese_count + 1, vector<double>(cheese_count + 1, 0.0));
for (int i = 0; i <= cheese_count; ++i) {
for (int j = i + 1; j <= cheese_count; ++j) {
distances[i][j] = distances[j][i] = distance_calculate(x_coords[i], y_coords[i], x_coords[j], y_coords[j]);
}
}
int total_states = 1 << cheese_count;
vector<vector<double>> dp(total_states, vector<double>(cheese_count + 1, INF));
for (int i = 1; i <= cheese_count; ++i) {
dp[1 << (i - 1)][i] = distances[0][i];
}
for (int mask = 1; mask < total_states; ++mask) {
for (int current = 1; current <= cheese_count; ++current) {
if (!(mask & (1 << (current - 1)))) continue;
for (int previous = 1; previous <= cheese_count; ++previous) {
if (current == previous || !(mask & (1 << (previous - 1)))) continue;
int previous_mask = mask ^ (1 << (current - 1));
dp[mask][current] = min(dp[mask][current], dp[previous_mask][previous] + distances[previous][current]);
}
}
}
double min_distance = INF;
int full_mask = total_states - 1;
for (int i = 1; i <= cheese_count; ++i) {
min_distance = min(min_distance, dp[full_mask][i]);
}
printf("%.2lf\n", min_distance);
return 0;
}
En un tablero de ajedrez de \(n \times n\), se deben colocar \(k\) reyes sin que se ataquen entre sí (ni adyacentes horizontal, vertical o diagonalmente). Se usa DP con compresión de estados: \(dp[i][j][s]\) representa el número de formas de colocar reyes hasta la fila \(i\), con \(j\) reyes usados, y el estado de la fila actual \(s\). Se verifican estados válidos donde no hay reyes adyacentes en la misma fila, y se asegura compatibilidad con la fila anterior usando operaciones bitwise.
#include #include using namespace std;
int main() { int board_size, king_target; cin >> board_size >> king_target;
vector<int> valid_row_states;
vector<int> king_counts(1 << board_size, 0);
auto check_validity = [&](int state) {
for (int col = 0; col < board_size - 1; ++col) {
if ((state >> col & 1) && (state >> (col + 1) & 1)) {
return false;
}
}
return true;
};
for (int state = 0; state < (1 << board_size); ++state) {
if (check_validity(state)) {
valid_row_states.push_back(state);
int count = 0;
for (int i = 0; i < board_size; ++i) {
if (state >> i & 1) count++;
}
king_counts[state] = count;
}
}
vector<vector<int>> compatible_states(valid_row_states.size());
for (int i = 0; i < valid_row_states.size(); ++i) {
int state_a = valid_row_states[i];
for (int j = 0; j < valid_row_states.size(); ++j) {
int state_b = valid_row_states[j];
bool compatible = true;
for (int col = 0; col < board_size; ++col) {
if (state_a >> col & 1) {
if (col > 0 && (state_b >> (col - 1) & 1)) compatible = false;
if (col < board_size - 1 && (state_b >> (col + 1) & 1)) compatible = false;
}
}
if (compatible) compatible_states[i].push_back(j);
}
}
vector<vector<vector<long long>>> dp(board_size + 2, vector<vector<long long>>(valid_row_states.size(), vector<long long>(king_target + 1, 0)));
dp[0][0][0] = 1;
for (int row = 1; row <= board_size + 1; ++row) {
for (int state_idx = 0; state_idx < valid_row_states.size(); ++state_idx) {
int current_state = valid_row_states[state_idx];
int kings_in_state = king_counts[current_state];
for (int used = kings_in_state; used <= king_target; ++used) {
for (int prev_idx : compatible_states[state_idx]) {
dp[row][state_idx][used] += dp[row - 1][prev_idx][used - kings_in_state];
}
}
}
}
cout << dp[board_size + 1][0][king_target] << endl;
return 0;
}
</div>Estos ejemplos ilustran cómo la compresión de estados permite manejar problemas con múltiples variables de estado de manera eficiente mediante bitmask en programación dinámica.