首先,我们将学习位屏蔽和动态编程,然后解决与之相关的问题,以解决您与实现有关的查询。
位掩码也称为掩码,是一个N位序列,用于编码我们集合的子集。掩码的元素可以设置或不设置(即0或1)。这表示位掩码中所选元素的可用性。例如,如果设置了掩码的第i位,则子集中的元素i可用。对于N个元素集,可以有一个2 N个掩码,每个掩码对应一个子集。
因此,为了解决该问题,我们将开始一个遮罩,即一个子集为其分配一个值,然后使用先前遮罩的值查找其他遮罩的值。使用此方法,我们最终将能够计算主集合的值。
为计算面罩的最佳解决方案,我们将以所有可能的方式删除一个元素并计算所有值,这些值将最终构成最终解决方案。
动态编程是一种优化方法,其中我们解决子问题并将其解决方案存储在其他重叠子问题中。
现在,让我们看看我们将使用位掩码和动态编程解决的问题
有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的掩码来使用位掩码和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