状压 DP

状态压缩用一个二进制整数记录集合：第 i 位为 1 表示第 i 个元素已选择。它适用于元素数较小（通常 n≤20）而集合状态很关键的问题。

位运算基础

mask>>i&1 判断第 i 位；mask|(1<<i) 加入元素；mask^(1<<i) 在已知存在时删除元素；mask&-mask 可取最低位的 1。

旅行商问题

令 dp[mask][u] 为从起点出发，访问 mask 中顶点且最后在 u 的最短路。枚举尚未访问 v，转移至 dp[mask|1<<v][v]。

for (int mask=1;mask<(1<<n);++mask)
 for (int u=0;u<n;++u) if (dp[mask][u]<INF)
  for (int v=0;v<n;++v) if (!(mask>>v&1))
   dp[mask|1<<v][v]=min(dp[mask|1<<v][v],dp[mask][u]+w[u][v]);

复杂度

上述 TSP 为 O(2ⁿn²) 时间、O(2ⁿn) 空间。若要枚举 mask 的所有子集，用 for(int s=mask;s;s=(s-1)&mask)，总量为 O(3ⁿ)，须先评估规模。

整理自 XOJ《状压DP》。