# 状态压缩DP-java描述

***

## 概念

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

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

二进制状压的可以将状态数压至 $ 2^n \* n $ ，时间复杂度为状态数X决策数n，所以时间复杂度为 $2^n\*n^2 $。

虽然看着很大，但还是远小于爆搜的n!复杂度。但由于复杂度很大，这种题目的特征是n的值非常小，一般范围只有两三位数。

## 位运算基础

状压使用位运算操作二进制数，从而检测或改变状态。常用的二进制位运算操作：

1. 判断一个数字x二进制下第i位是不是等于1。（最低第1位）

方法：`if((( 1<<(i−1) ) & x)>0)` 将1左移i-1位，相当于制造了一个只有第i位 上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0， 说明x第i位上是1，反之则是0。

1. 将一个数字x二进制下第i位更改成1。

方法：`x=x|(1<<(i−1))`证明方法与1类似。

1. 将一个数字x二进制下第i位更改成0。

方法：`x=x&~(1<<(i−1))`

1. 把一个数字二进制下最靠右的第一个1去掉。

方法：`x=x&(x−1)`

## 例题

![例题](https://img-blog.csdnimg.cn/20200223190918412.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjYyMTE1,size_16,color_FFFFFF,t_70)

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200223190931850.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjYyMTE1,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200223190941474.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjYyMTE1,size_16,color_FFFFFF,t_70)

### 二进制状态表示

转换为二进制数为 \[111..11] 表示全部都选的状况

转换为二进制数为 \[000..00] 表示全都不选的状况

\[11001] 表示选第1,4,5个

### 转移方程

首先考虑循环，我们依次考虑每个包裹 `i`，是第一层；

在考虑包裹 `i` 时，从下到上，从已存在推未存在的状态，对所有已存在的状态 `j` 做分析，看选这个包裹是否对这个状态有影响。

设读入的每个包裹包含的种类的数据为`data[]`

设`dp[l] = k`为想要获得`l`（二进制表示）状态对应的糖果种类，至少要选取`k`个包裹。

所以，得到转移方程为：

```java
dp[j | data[i]] = dp[j] + 1;
```

其中，`j|data[i]`的意义为取了这个包裹后小明手上有的糖果种类状态。（由原状态在`data[i]`不为0的位上置1）

### 完整代码

详细说明见注释。

```java
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状态的值
	}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/suan-fa/zhuang-tai-ya-suo-dpjava-miao-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.