状态压缩DP-java描述

概念

状态压缩是一种利用二进制数来对状态进行压缩的方式。状态压缩之后，我们可以通过整数的加减来表示状态之间的转移。整数和状态一一对应。

一般而言，状态压缩用于解决非常多阶段的动态规划问题。

二进制状压的可以将状态数压至 $ 2^n * n $ ，时间复杂度为状态数X决策数n，所以时间复杂度为 $2^n*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状态的值
	}

最后更新于1年前