C ++中的位屏蔽和动态编程

首先,我们将学习位屏蔽和动态编程,然后解决与之相关的问题,以解决您与实现有关的查询。

位掩码也称为掩码,是一个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