6956: 学习系列 —— 动态规划 —— 状压 DP
[Creator : ]
Description
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 状态定义
dp[i]5.2 转移方程
5.3 模板
for(int S = 0 ; S<(1<<n) ; S++)
{
for(int i = 0 ; i<n; i++)
{
if(S&(1<<i)){
for(int j = 0; j<n; j++)
{
if(!(s & (1 << j)&&G[i][j])
dp[j][S|(1 << j)]=min(dp[j][S|(1<<i)],dp[i]+G[i][j])
}
}
}
}