首页 > 其他分享 >状态压缩 DP 学习笔记【入门篇】

状态压缩 DP 学习笔记【入门篇】

时间:2022-08-26 02:03:29浏览次数:74  
标签:texttt 运算 二进制 状压 笔记 入门篇 DP dp

前言

状态压缩 DP,简称状压 DP

之前一直觉得状压特别难,学了一下,发现基本形态挺简单的。

在学习之前,你需要掌握:

  1. 简单 DP(如线性 DP,背包)
  2. 基本二进制运算:& 运算、| 运算、\(\oplus\) 运算、左右移运算符。

什么是状压 DP

状态压缩,顾名思义,就是对当前的状态压缩。

怎么压缩呢?答案是二进制。

比如一个简单的例子:我有五个小球,依次编号 \(0\) 到 \(5\)。

我想表达『选 \(1\) 号与 \(3\) 号球』,怎么压缩?

很显然,对应二进制是 \((01010)_2\),转换成十进制就是 \(10\)。

这个就是状压 DP。

也就是说,状态的转移(二进制转移),可以变成整数的加减(十进制加减)。

二进制运算

既然都有二进制,二进制的简单技巧肯定少不了。

二进制数 \(x\),第 \(n\) 位是否为 \(k\)

此处 \(k\) 取值 \(1\) 或 \(0\)。

将 \(x\) 右移 \((n-1)\) 位,即 \(x >> (n-1)\)。

此时,\(x\) 的末位就是第 \(n\) 位,拉出个位即可:\(x >> (n-1)\) & $ 1$。

所以判断语句即为:if ( (x >> (n-1) & 1) == k)

* 在打代码时,需要注意括号。位运算优先级较为复杂,保险起见可以打括号,但必须保证可读性。

二进制数 \(x\),修改第 \(n\) 位为 \(1\)

利用或运算求解。

将第 \(n\) 位修改成 \(1\),相当于 \(x\) | \(100\cdots00\),应该有 \((n-1)\) 个 \(0\)。

所以修改语句即为:x | (1 << (n-1))

二进制数 \(x\) 最低位的 \(1\) 改成 \(0\)

比如说,将 \((100101)_2\) 修改为 \((100100)_2\) ,将 \((110100)_2\) 修改为 \((110000)_2\)。

方法一:利用 \(\texttt{lowbit()}\) 修改:x - (x&-x)。其中的 \(\texttt{lowbit()}\) 在树状数组中有使用,不理解没关系。

方法二:

对于一个数 \(x\),\((x-1)\) 总是等于:将末尾 \(0\) 变成 \(1\),最低位 \(1\) 变成 \(0\),前面不变。

所以,x & (x-1) 就是答案。

你可能听不懂,那么举个例子。

若 \(x = (110\space100)_2\),则 \((x - 1) = (110\space 001)_2\)。

容易发现,前三位进行 & 运算,不变;后三位进行 & 运算,必为 \(0\)。

这下懂了吧!

状压 DP 思路

一般地,状态都用一个二维数组 dp[][] 表示。

\(dp_{i, j}\) 的第一维 \(i\),通常是二进制数,表示哪些物品被选过。

第二维 \(j\) 则比较多变,需要根据题目转换。

这里还需要知道一个东西:\(i\) 的取值范围

假如一共有 \(n+1\) 个点,编号 \(0\) 至 \(n\),则 \(i = [0, 2^0 + 2^1 + \cdots + 2^n]\)。

后半段的 \(2^0 + 2^1 + \cdots + 2^n\) 是等比数列,简单普及一下求解方法。

令 \(S = 2^0 + 2^1 + \cdots + 2^n\)。

则 \(2\cdot S = 2^1 + 2^2 + \cdots + 2^n + 2^{n+1}\)。

两式相减得:\(2\cdot S - S = 2^{n+1} - 2^0\)。

简化得:\(S = 2^{n+1} - 1\)。

大家肯定还是不理解,我们来看一道经典例题。

经典例题 - TSP 问题

题意

前置知识:\(\texttt{Floyd}\) / \(\texttt{dijkstra}\) 算法。

旅行商问题(Traveling salesman problem,即 TSP),是组合优化中的 NP 问题。

至今还没有多项式解法,仅有指数级做法。

具体问题如下:

有一张图(一般为无向图),保证所有点均连通。

有一个旅行商在 \(0\) 号点,要求他从 \(0\) 号点出发,访问过所有的城市并回到原点。

给定每对城市之间的距离,求出最短路。

如果用暴力,时间复杂度过高。

所以使用状压 DP 实现。


思路

首先,看图的稠密性决定使用 \(\texttt{floyd}\) 还是 \(\texttt{dijkstra}\)。

反正,用最短路算法,求出任意两点的最短距离。

设 \(dp_{i, j}\) 表示行走过的点的状态为 \(i\)(对应二进制数),最后一个点是 \(j\) 号点。

我们可以枚举 \(k = [0, \texttt{maxn}]\)。

接下来再枚举 \(i\) 与 \(j\),表示几号点。

我们可以大致写出有关 \(i \to j\) 的状态转移方程:

如果 \(k\) 的第 \(j\) 位为 \(0\),说明可以尝试转移:

\[\color{black}{dp[\space}\color{red}{k | (1<<n)}\color{black}{\space}][\space j\space] = \min\begin{cases}\color{black}{dp[\space}\color{red}{k | (1<<n)}\color{black}{\space ][\space j\space]}\\\\ \color{black}{dp[\space}\color{red}{k}\color{black}{\space ][\space i\space]} + e_{j, i}\end{cases} \]

啊这个方程写崩溃了。

最后的答案即为:\(dp[\texttt{maxn}][0]\)。

对了,不要忘记初始化 \(dp_{i, j} = \infty\),\(dp_{0, 0} = 0\)。


代码

给出代码。

大致讲一下这份代码的读入格式。

第一行 \(n\) 表示有 \((n+1)\) 个点,编号 \(0\) 至 \(n\)。

接下来一个 \((n+1)\times(n+1)\) 的矩阵,矩阵的第 \(i\) 行 \(j\) 列表示 \(dis[i \to j]\)。

道路是单向的。

这里由于图是稠密图,所以使用 \(\texttt{floyd}\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 0x3f3f3f3f
#define N 20
using namespace std;
int n, e[N][N], dp[1<<N][N];
void Input()
{
	scanf("%d", &n);
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			scanf("%d", &e[i][j]);	
}
void floyd()
{
	for (int k = 0; k <= n; k++)
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
}
void DP()
{
	memset(dp, INF, sizeof(dp));
	dp[0][0] = 0;
	int maxn = (1 << n+1) - 1;
	for (int k = 0; k <= maxn; k++)
		for (int i = 0; i <= n; i++)
				for (int j = 0; j <= n; j++)
					if ( ((k >> j) & 1) == 0) //判断第 j 位是否为 0。
						//把第 j 位改成 1。
						dp[ k|(1<<j) ][j] = min(dp[ k|(1<<j) ][j], dp[k][i] + e[j][i]);
	printf("%d", dp[maxn][0]);
}
int main()
{
	Input();
	floyd();
	DP();
}

进一步思考

通过这道题目,我们发现:状压 DP 的时间复杂度一般是 \(O(2^n \cdot n^2)\)。

由此可得,状压 DP 的适用范围不会很广,\(n\le20\) 左右。

如果 \(n\) 再大一点,不说时间问题,空间都爆炸啦(空间至少需要 \(2^n\),本题空间 \(2^n \cdot n + n^2\))!

考虑到这个后,你就可以一眼知道,一道 DP 题有没有使用状压 DP 的可能性。

后记

貌似没有实战例题,以后有时间再补例题吧。

状压 DP 真的不难,希望大家努力学会!

此外,推荐两道状压入门题:link1 & link2

还有大神整理的题单:link

首发:2022-06-12 17:34:29

标签:texttt,运算,二进制,状压,笔记,入门篇,DP,dp
From: https://www.cnblogs.com/liangbowen/p/16622884.html

相关文章

  • 拓扑排序学习笔记
    前言在学习这篇文章之前,你需要了解的算法有:基本图论知识链式前向星(图的一种存储方式)了解队列、栈等简单数据结构的实现,用STL也行。什么是拓扑排序AOV网的定义......
  • 05.爬虫入门笔记1
    入门爬虫笔记011.request库的使用使用request库的get方法importrequestr=request.get('www.baidu.com')这会得到一个Response对象,将其存入变量r。显示得到的......
  • 基于 .NET 6 的轻量级 Webapi 框架 FastEndpoints
    大家好,我是等天黑。FastEndpoints 是一个基于.NET6开发的开源webapi框架,它可以很好地替代.NETMinimalAPIs和MVC,专门为开发效率而生,带来了全新的开发模式和编......
  • SSCMS文件解析-学习笔记
    //声明常量,不可变constfs=require('fs-extra');//初始化目录插件constdel=require('del');//删除文件的工具constgulp=require('gulp');//基于流的代码自动化......
  • 电子笔记本的思考(1)(ver0.4)
    章节: 电子笔记本的思考(1)(ver0.4)上面的是截屏的完整版,分割线下面的是纯文字版本: 作者姓名(本人的真实姓名):胡佳吉居住地:上海作者网名:EverSteins版权声明:电子笔记本的......
  • 【DP】决策单调性小记
    何谓决策单调性?指的就是在最优化dp中,状态的最优转移点单调不减的性质。这使得我们在做dp的时候可以减少冗余计算以达到优化的效果。这类优化方法常用于分段问题。0x......
  • 线程池ThreadPoolExecutor
    线程池ThreadPoolExecutor1、线程池介绍1.1线程池概念Sun在Java5中,对Java线程的类库做了大量的扩展,其中线程池就是Java5的新特征之一,除了线程池之外,还有很多多线程相关......
  • 学习笔记270—Excel如何快速批量将中文名字转换为拼音?
    Excel如何快速批量将中文名字转换为拼音?在excel表格中,我们可以通过内置的功能来进行拼音的编辑,但无法直接批量地转换中文为拼音。当然,这里是跳过了vba的用法,因为vba要求......
  • 性能测试学习笔记——工具的使用,性能测试流程
    性能测试学习笔记一、为什么要做性能测试:因为功能和接口测试只能验证软件的功能是否正常运行,功能和接口测试不能验证软件的性能在多用户,多并发,长时间的操作下,能否正常运......
  • Pendo for Mac v6.1.5中文版 云笔记软件
    前言哪里有轻量小巧的mac云笔记软件?PendoforMac是马克喵搜集到的一款运行在Mac平台上的一款新颖精美的mac云笔记软件。PendoMac版是Mac平台上的一款效率办公软件,Pend......