赞
踩
相信在学完动态规划之后,就会接触到动态规划的许多进阶的版本,这里我将简单讲讲状压dp,顾名思义,状压,为什么叫状压~就是状态压缩,就是一种优化动态规划算法的技术,通常用于处理状态空间较大的问题。在状压动态规划中,我们会使用较小的数据结构来表示状态,并利用位运算来进行状态转移和计算,从而减少内存消耗和提高计算效率。具体来说,状压动态规划通常会使用整数来表示状态,其中整数的每一位对应于问题中的某种特定情况或特征。通过位运算,我们可以高效地表示和操作大量的状态,并且可以利用位运算的性质来进行状态转移和计算,从而减少时间和空间复杂度。状压动态规划通常用于处理状态空间较大的问题,例如组合优化问题、子集相关问题等。通过使用状压动态规划,我们可以更高效地解决这些问题,并且可以在一定程度上降低算法的时间复杂度和空间复杂度。
总的来说,状压动态规划是一种优化动态规划算法的技术,通过使用整数来表示状态并利用位运算来进行状态转移和计算,以提高算法的效率和性能。
在介绍完状压dp的概念之后,现在咱来回顾几个用得上的语法内容,因为在许多数据结构之中是用的比较少的。首先来回顾"<<"
这是个什么?嗯,在C++中,<< 是位移运算符,用于将一个数的所有位向左移动指定的位数。在计算机编程中,左移运算符 << 不是表示数学上的指数运算,而是表示对数字进行位移操作。具体来说,对于整数 n,n << m 表示将 n 的二进制表示向左移动 m 位,相当于将 n 乘以 2 的 m 次幂。因此,1 << 20 表示将数字 1 左移 20 位,相当于将 1 乘以 2 的 20 次幂。这并不等同于数学上的指数运算,而是位运算的结果在这种情况下,1
<<20
表示将整数1向左移动20位,相当于计算2的20次方,结果为1048576。表达式 2 << 10 表示将数字 2 左移 10 位。在计算机中,左移运算符 << 会将一个数的二进制表示向左移动指定的位数,相当于将这个数乘以 2 的指定次幂。因此,2 << 10 的结果是 2 乘以 2 的 10 次幂,即 2 的 10 次方,结果为 1024。
OK,<<相信大家了解差不多了吧,那现在就介绍"|":
在C++中,竖线(|)运算符代表按位或运算。它用于对两个整数的每个对应位执行逻辑或操作,返回的结果是两个数对应位上的逻辑或结果。例如,对于两个二进制数a和b,a | b将返回一个新的二进制数,其中每个位上的值是a和b对应位上值的逻辑或结果。
例如:
a = 5; // 二进制表示为 0101
b = 3; // 二进制表示为 0011
c = a | b; // c的值为 7,二进制表示为 0111
在上面的示例中,a | b的结果是7,因为在二进制表示中,对应的位上进行了逻辑或操作。
上文是一些基础知识,那回顾一下memset一个stl容器用于将一块内存空间设置为指定的值:一般的用法void *memset(void *ptr, int value, size_t num);
ptr
是指向要设置值的内存起始地址的指针。value
是要设置的值,通常是一个无符号字符。num
是要设置的字节数。这些东西回顾完了,其实在面对状压dp的时候的步骤和动态规划的差不多,只不过要多进行一个'|'操作进行状态压缩。干说是不是有点不太好理解下面上题目:
题目描述
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述,我们将 M 种 口味编号 1 ∼ M。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果,而 是 K 颗一包整包出售。
幸好糖果包装上注明了其中 K 颗糖果的口味,所以小明可以在买之前就知 道每包内的糖果口味。
给定 N 包糖果,请你计算小明最少买几包,就可以品尝到所有口味的糖 果。
输入格式
第一行包含三个整数 N、M 和 K。
接下来 N 行每行 K 这整数 T1, T2, · · · , TK,代表一包糖果的口味
(对于 30% 的评测用例,1 ≤ N ≤ 20 。
对于所有评测样例,1 ≤ N ≤ 100,1 ≤ M ≤ 20,1 ≤ K ≤ 20,1 ≤ Ti ≤ M 。)
输出格式
一个整数表示答案。如果小明无法品尝所有口味,输出 −1。
样例输入
复制
6 5 3 1 1 2 1 2 3 1 1 3 2 3 5 5 4 2 5 1 2样例输出
复制
2
分析完题目,发现数据还挺好的咱可以用 n位二进制数来表示所购买糖果中 n 种口味的组合情况。
其中有1是不是就是代表有这个糖果,0就是没有?好好理解一下。
那咱怎样确定dp呢?嗯~既然要用01这种二进制来表示全部情况,我们可以用dp[i]:表示状态为i时所需的最小糖果包数。状态i表示口味的组合情况,每个口味对应状态中的一位。dp数组记录了每种口味组合所需的最小糖果包数,通俗一点讲用一个二进制数来表示口味的组合情况。比如,如果口味有4种,那么0001表示只包含口味1,1010表示包含口味2和口味4。dp[i]表示当口味组合为i时,所需的最小糖果包数。也就是说,dp数组记录了每种口味组合所需的最小糖果包数。
OK代码如下
- #include <iostream>
- #include <cstring>
- using namespace std;
-
- const int MAX_N = 20;
-
- int main() {
- int n, m, k;
- int dp[1 << MAX_N]; // 使用状压的数组需要开2^n,因为表示的是状态
- int v[MAX_N]; // 记录每种糖果的口味状态
-
- // 读入口味种类数n、糖果总种类数m、每种糖果的口味数k
- cin >> n >> m >> k;
-
- // 初始化dp数组为一个较大的数,表示无穷大
- memset(dp, 0x3f, sizeof(dp));
-
- // 读入每种糖果的口味状态
- for (int i = 0; i < n; ++i) {
- int flavors = 0;
- for (int j = 0; j < k; ++j) {
- int flavor;
- cin >> flavor;
- flavor--; // 口味从1开始,数组从0开始,需要减1
- flavors |= (1 << flavor); // 使用按位或操作记录口味状态
- }
- dp[flavors] = 1; // 这些口味都可以用一包糖解决
- v[i] = flavors; // 记录糖的状态
- }
-
- // 状态转移,枚举所有可能的状态
- for (int i = 0; i < (1 << m); ++i) {
- for (int j = 0; j < n; ++j) {
- dp[i | v[j]] = min(dp[i | v[j]], dp[i] + 1); // 更新dp数组的值
- }
- }
-
- // 输出结果
- if (dp[(1 << m) - 1] == 0x3f3f3f3f) {
- cout << -1; // 无法搭配出来
- } else {
- cout << dp[(1 << m) - 1]; // 搭配出来所需的最少糖果包数量
- }
-
- return 0;
- }
这样就通过一个状压dp解决啦这个题目,由于本人水平有限,有错误指出还恳请各位指出^_^
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。