SaroProck ⚡
【动态规划】状态压缩DP

【动态规划】状态压缩DP

Sat Jun 10 2023
6 分钟
技术 OI学习笔记 动态规划 优化 状态压缩 DP 动态规划 cpp OI
1092 字

前言#

二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个 int 整形是 4 个字节，也就是 32 位 bit，我们通过这 32 位 bit 上 0 和 1 的组合可以表示多大 21 亿个不同的数。如果我们把这 32 位 bit 看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。那么我们可不可以用一个数来保存一维的 DP 状态呢？

这当然是可行的，动态规划的过程是随着阶段的增长，在每一个状态维护上不断扩展的。而对于某些题目，我们扩展时需要记录一个状态集合，保存状态信息，以便进行状态转移。而状态压缩则是把这一个大小不超过 N、元素小于 K 的集合看做是一个 N 位的 K 进制数，以一个[0,KN−1][0, K^N - 1]之间的十进制整数的形式作为 DP 状态的一维。这样我们就可以只用一个十进制整数，就保存了一个状态信息——这就是状态压缩。

状态压缩的题目一般只有两种状态（当然也有三种状态的三进制题目）。这里只讨论最常见的二进制状态压缩，K 进制状态压缩可以以此类推，不再赘述。

集合操作#

在二进制状态 DP 中，我们用一个十进制整数代表一个集合，例如：9−>(1001)29 -> (1001)_{2} ，可以等效替换为一个 bool 数组B[4]={1,0,0,1}B[4] = \{1, 0, 0, 1\}。下面是集合的常用操作：

| 操作含义 | 代码 | | :abbrlink: 122ed47c mathjax: true categories:

-----------------------------------: | :----------------: | | 取出整数 n 在二进制表示下的第 k 位 | (n >> k) & 1 | | 取出整数 n 在二进制表示下的第 0k-1 位（后 k 位） | n & ((1 << k) - 1) | | 把整数 n 在二进制下表示的第 k 位取反 | n ^ (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 1 | n| (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 0 | n & ( (1 << k)) | | 判断整数 n 在二进制表示下的第 k 位是否为真 | n & (1 << (k - 1)) |

注意了！我们常说的第一位在二进制表示下其实是第零位，程序实现时一定要注意当前真正在操作的是哪一位，否则 WA 了很难找出错误。

上机实践#

售货员的难题#

经典例题，状态压缩 DP 入门题：P1171 售货员的难题。

构思（朴素算法）#

看一下题目……最短路是吧？但是要求经过所有结点。

所以优先队列 BFS 最短路这种就不管用啦！那么既然要走过所有村庄，直接枚举全排列输出，暴力省事。时间复杂度为O(N∗N!)O(N * N!)，属于是必死无疑。

下面给出一段基础搜索代码，包含基础剪枝，得分80Pt80Pt.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
using namespace std;
int lxy[21][21],hrb[21];
int n,i,j,k,minn=1e9;

int ss(int x,int y,int z)//x表示村子编号，y表示走了几个村子，z表示用的时间
{
    if(z > minn) return 0;//基本最小值剪枝
    if(y == n && z + lxy[x][1] < minn)
    {
	minn = z + lxy[x][1];
	return 0;
    }//比较求最小值，其中的加lxy[x][1]意思是走回第一个村
    for(int i = 2; i <= n; i++)//循环开始
    {
	if(hrb[i]==0&&i!=x)//深搜模板，没走就搜
	{
	    hrb[i] = 1;//打上标记
	    ss(i,y + 1, z + lxy[x][i]);
	    hrb[i] = 0;//回溯
        }
    }
    return 0;
}

int main()
{
    scanf("%d", &n);
    for(i = 1;i <= n; i++)
	for(k = 1;k <= n; k++)
	    scanf("%d", &lxy[i][k]);//输入
    ss(1, 1, 0);//开搜
    printf("%d",minn);
}