C ++中的位屏蔽和动态编程
首先，我们将学习位屏蔽和动态编程，然后解决与之相关的问题，以解决您与实现有关的查询。
位掩码也称为掩码，是一个N位序列，用于编码我们集合的子集。掩码的元素可以设置或不设置（即0或1）。这表示位掩码中所选元素的可用性。例如，如果设置了掩码的第i位，则子集中的元素i可用。对于N个元素集，可以有一个2 N个掩码，每个掩码对应一个子集。
因此，为了解决该问题，我们将开始一个遮罩，即一个子集为其分配一个值，然后使用先前遮罩的值查找其他遮罩的值。使用此方法，我们最终将能够计算主集合的值。
为计算面罩的最佳解决方案，我们将以所有可能的方式删除一个元素并计算所有值，这些值将最终构成最终解决方案。
动态编程
动态编程是一种优化方法，其中我们解决子问题并将其解决方案存储在其他重叠子问题中。
现在，让我们看看我们将使用位掩码和动态编程解决的问题
问题
有50个帽，数字从1到50。N个人的收藏中有其中一些帽。有一天，他们所有人都戴着帽子参加聚会。但是所有人都需要看起来独特，因此，他们决定分别佩戴不同编号的帽子。在集合中给定了n个人数和上限编号。我们的任务是找到佩戴帽子的总数，以使每个人看起来都独一无二。
在问题中，第一行包含值n，即人数。接下来的n行包含其集合。
输入-
34 45 10
25
45 10
输出-
4
说明-
所有可能的方式是(4,25,45)，(4,25,10)，(45,25,10)，(10,25,45)。
输出应采用1000000007的形式，因为方式数量可以很多。
为了解决这个问题，一个简单的解决方案是找到所有使用帽子的人的可能组合。从第一个集合开始，然后重复其余的集合。但是此解决方案尚未优化。
更好的解决方案是通过为10个人创建大小为210的掩码来使用位掩码和DP。还有一个大小为51的上限的向量。然后，我们将以多种方式重现。
示例
展示解决方案实施方案的程序-
#include<bits/stdc++.h>using namespace std;
vector<int> caps[101];
int dp[1025][101];
int allmask;
long long int uniqueCaps(int mask, int i) {
if (mask == allmask) return 1;
if (i > 100) return 0;
if (dp[mask][i] != -1) return dp[mask][i];
long long int ways = uniqueCaps(mask, i+1);
int size = caps[i].size();
for (int j = 0; j < size; j++) {
if (mask & (1 << caps[i][j])) continue;
else ways += uniqueCaps(mask | (1 << caps[i][j]), i+1);
ways %= (1000000007);
}
return dp[mask][i] = ways;
}
int main() {
int n = 3;
//收集人1-
caps[4].push_back(0);
caps[45].push_back(0);
caps[10].push_back(0);
//收集人2-
caps[25].push_back(1);
//收集人3-
caps[45].push_back(2);
caps[10].push_back(2);
allmask = (1 << n) - 1;
memset(dp, -1, sizeof dp);
cout<<"The number of ways the person can wear unique cap in party is:\t"<<uniqueCaps(0, 1);
return 0;
}
输出结果
The number of ways the person can wear unique cap in party is: 4
以上是 C ++中的位屏蔽和动态编程 的全部内容， 来源链接： utcz.com/z/326728.html
