数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中的位掩码和动态规划
首先，我们将学习位掩码和动态规划，然后我们将解决一个相关的问题，这将解决您与实现相关的疑问。
位掩码，也称为掩码，是 N 位的序列，用于编码集合的子集。掩码的元素可以是设置的或未设置的（即 0 或 1）。这表示位掩码中所选元素的可用性。例如，如果掩码的第 i 位被设置，则元素 i 在子集中可用。对于 N 个元素的集合，可以有 2N 个掩码，每个掩码对应一个子集。
因此，为了解决问题，我们将从一个掩码（即子集）开始，为其分配一个值，然后使用先前掩码的值查找后续掩码的值。使用此方法，我们将最终能够计算主集合的值。
为了计算掩码的最优解，我们将以所有可能的方式移除一个元素，并计算所有这些值，这些值将最终有助于最终解。
动态规划
动态规划是一种优化方法，其中我们解决子问题并将它们的解存储起来，以便在其他重叠的子问题中使用。
现在，让我们来看一个我们将使用位掩码和动态规划来解决的问题
问题
有 50 个帽子，编号从 1 到 50。N 个人在其收藏中有一些帽子。有一天，他们都戴着帽子去参加派对。但所有人都需要看起来独一无二，所以他们决定每个人都戴不同号码的帽子。我们得到 n 个人的数量以及他们收藏中的帽子号码。我们的任务是找到他们可以戴帽子的总方法数，以便每个人看起来都独一无二。
在这个问题中，第一行包含值 n，即人数。接下来的 n 行包含他们的收藏。
输入 −
3 4 45 10 25 45 10
输出 −
4
说明 −
所有可能的方法是(4, 25, 45) , (4, 25, 10), (45, 25, 10), (10, 25, 45)。
输出应为 1000000007 的形式，因为方法的数量可能很大。
要解决此问题，一个简单的解决方案是使用帽子查找所有可能的人员组合。从第一个集合开始，递归其余集合。但此解决方案未经优化。
更好的解决方案是使用位掩码和动态规划，为 10 个人创建一个大小为 210 的掩码。以及大小为 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;
// Collection of person 1
caps[4].push_back(0);
caps[45].push_back(0);
caps[10].push_back(0);
// Collection of person 2
caps[25].push_back(1);
// Collection of person 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
3K+ 次浏览
