概念
状态压缩是一种利用二进制数来对状态进行压缩的方式。状态压缩之后，我们可以通过整数的加减来表示状态之间的转移。整数和状态一一对应。
一般而言，状态压缩用于解决非常多阶段的动态规划问题。
二进制状压的可以将状态数压至 $ 2n * n $ ，时间复杂度为状态数X决策数n，所以时间复杂度为 $2n*n^2 $。
虽然看着很大，但还是远小于爆搜的n!复杂度。但由于复杂度很大，这种题目的特征是n的值非常小，一般范围只有两三位数。
位运算基础
状压使用位运算操作二进制数，从而检测或改变状态。常用的二进制位运算操作：
- 判断一个数字x二进制下第i位是不是等于1。（最低第1位）
方法：if((( 1<<(i−1) ) & x)>0)将1左移i-1位，相当于制造了一个只有第i位 上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0， 说明x第i位上是1，反之则是0。
- 将一个数字x二进制下第i位更改成1。
方法：x=x|(1<<(i−1))证明方法与1类似。
- 将一个数字x二进制下第i位更改成0。
方法：x=x&~(1<<(i−1))
- 把一个数字二进制下最靠右的第一个1去掉。
方法：x=x&(x−1)
例题
二进制状态表示
转换为二进制数为 [111..11] 表示全部都选的状况
转换为二进制数为 [000..00] 表示全都不选的状况
[11001] 表示选第1,4,5个
转移方程
首先考虑循环，我们依次考虑每个包裹 i，是第一层；
在考虑包裹 i 时，从下到上，从已存在推未存在的状态，对所有已存在的状态 j 做分析，看选这个包裹是否对这个状态有影响。
设读入的每个包裹包含的种类的数据为data[]
设dp[l] = k为想要获得l（二进制表示）状态对应的糖果种类，至少要选取k个包裹。
所以，得到转移方程为：
dp[j | data[i]] = dp[j] + 1;
其中，j|data[i]的意义为取了这个包裹后小明手上有的糖果种类状态。（由原状态在data[i]不为0的位上置1）
完整代码
详细说明见注释。
public static void main(String[] args) {
int n,m,k;
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); m = sc.nextInt(); k = sc.nextInt();
int[] data = new int[n];
int[] dp = new int[1<<k];
//初始化，全初始为-1表示没算过不存在，除了起点
Arrays.fill(dp, -1); dp[0] = 0;
for(int i =1; i<=n; i++) {
for(int j = 1;j<=k;j++) {
//读入数据，并以二进制数表示
data[i] = data[i] | (1 << (sc.nextInt()-1));
//这里1 << (sc.nextInt()-1) 即构建二进制表示的过程
//如输入为3，则1左移2位，变为100，表示只选第三个包裹
}
//顺手把只选取这个包裹里的糖果种类的状态的dp设为1
//因为只选取这个包裹里的糖果种类自然只需要拿1次这个包裹就行了
dp[data[i]] = 1;
}
//开始dp
for(int i=1;i<=n;i++) { //依次针对每个包裹分析
for(int j =0;j<(1<<m);j++) { //针对每种状态分析
//注意这里for的边界条件是1<<m，之前读数据二进制的时候是1<<(x-1)
//1<<m其实有m+1位，所以这里所有数都小于1<<m,且正好小于。
if(dp[j]== -1)continue; //状态不存在的时候跳过，因为是从下往上推，不存在就没法推
//下面是其转移的目标的情况分析
//1. 目标状态不存在，直接算出目标的dp值
//2.目标状态存在，需要判断我们推的值能不能小于已有dp值，如果小于则替换
if(dp[j | data[i]] == -1 || dp[j] +1 < dp[j|data[i]])
dp[j|data[i]] = dp[j] +1; //这里j|data[i]是原来j状态用了i包裹而推算出的目标状态
}
}
System.out.println(dp[(1 << m) - 1]); //输出111..11状态的值
}