当前位置:   article > 正文

动态规划之状压dp

动态规划之状压dp

  相信在学完动态规划之后,就会接触到动态规划的许多进阶的版本,这里我将简单讲讲状压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代码如下

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. const int MAX_N = 20;
  5. int main() {
  6. int n, m, k;
  7. int dp[1 << MAX_N]; // 使用状压的数组需要开2^n,因为表示的是状态
  8. int v[MAX_N]; // 记录每种糖果的口味状态
  9. // 读入口味种类数n、糖果总种类数m、每种糖果的口味数k
  10. cin >> n >> m >> k;
  11. // 初始化dp数组为一个较大的数,表示无穷大
  12. memset(dp, 0x3f, sizeof(dp));
  13. // 读入每种糖果的口味状态
  14. for (int i = 0; i < n; ++i) {
  15. int flavors = 0;
  16. for (int j = 0; j < k; ++j) {
  17. int flavor;
  18. cin >> flavor;
  19. flavor--; // 口味从1开始,数组从0开始,需要减1
  20. flavors |= (1 << flavor); // 使用按位或操作记录口味状态
  21. }
  22. dp[flavors] = 1; // 这些口味都可以用一包糖解决
  23. v[i] = flavors; // 记录糖的状态
  24. }
  25. // 状态转移,枚举所有可能的状态
  26. for (int i = 0; i < (1 << m); ++i) {
  27. for (int j = 0; j < n; ++j) {
  28. dp[i | v[j]] = min(dp[i | v[j]], dp[i] + 1); // 更新dp数组的值
  29. }
  30. }
  31. // 输出结果
  32. if (dp[(1 << m) - 1] == 0x3f3f3f3f) {
  33. cout << -1; // 无法搭配出来
  34. } else {
  35. cout << dp[(1 << m) - 1]; // 搭配出来所需的最少糖果包数量
  36. }
  37. return 0;
  38. }

这样就通过一个状压dp解决啦这个题目,由于本人水平有限,有错误指出还恳请各位指出^_^

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/672996
推荐阅读
相关标签
  

闽ICP备14008679号