1 特别提醒

在涉及到位运算时，一定要注意位运算的优先级。该加的括号一定要加。

2 状态压缩

是利用计算机二进制的性质来描述状态的一种方式。
有二进制数 100011011（九位），每一位表示该位是否被占用，$1$ 表示用了，$0$ 表示没用，这样一种状态就被我们表示出来了

所以我们最多只需要 $2^{n + 1} - 1$ 的十进制数就好（二进制形式是 $n$ 个 $1$）。

3 定义

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

4 状压入门

4.1 问题

有 $n$ 件物品和一个容量为 $v$ 的背包。放入第 $i$ 件物品的占的空间为 $C_i$，得到的价值是 $W_i$。求解每种放法的背包价值？
当然这不是一个典型的动态规划问题，但是用动态规划的思想有助于讲解状压 DP。

4.2 定义状态

因为这个要求每一种放法的背包价值，所以我们状态应该是这 $n$ 件物品的放与不放的情况。
最容易想到的是开个 $n$ 维数组，第 $i$ 个维度的下标如果是 $1$ 的话代表放第 $i$ 件物品，$0$ 的话代表不放第 $i$ 件物品；
但是这样很容易造成空间浪费，而且多维数组也不好开。
我们仔细观察就会发现，每件物品有放与不放两种选择。
假设我们有 $5$ 件物品的时候，用 $1$ 和 $0$ 代表放和不放。如果这 $5$ 件物品都不放的话，那就是 00000；如果这 $5$ 件物品都放的话，那就是 11111。
我们知道可以用二进制表示所有物品的放与不放的情况；如果这些二进制用十进制表示的话就只有一个维度了。而且这一个维度能表示所有物品放与不放的情况；这个过程就叫做状态压缩。
细节：观察可以知道在上面的例子中 00000 ~ 11111 可以代表所有的情况，转化为十进制就是 0 到 ((1<<5)- 1)。

5 代码框架

5.1 状态定义

$\text{dp}[i][\text{S}]$
表示当前在节点 i，已经访问过结点集合为 S，所经过路径的最小权值和。用 S 表示集合即所谓的“状态压缩”。（只关心路过节点集合和当前节点，不记录路径）

5.2 转移方程

5.3 模板

for(int stat = 0 ; stat<(1<<n) ; stat++)
{
    for(int i = 0 ; i<n; i++) 
    {
        if(stat&(1<<i)){
            for(int j = 0; j<n; j++)
            {
                if(!(stat & (1 << j)&&G[i][j])
                    dp[j][j|(1 << j)]=min(dp[j][stat|(1<<i)],dp[i][stat]+G[i][j])
            }
        }
     }
}

6956: 学习系列 —— 动态规划 —— 状压 DP

Description