考虑下面的问题陈述。
null
共有100种不同类型的瓶盖，每个瓶盖都有一个从1到100的唯一id。此外，还有“n”个人，每个人都有不同数量的帽子。有一天，所有这些人都决定戴一顶帽子参加聚会，但为了看起来与众不同，他们决定没有一个人会戴同样类型的帽子。所以，数一数总的安排或方式，这样他们就不会戴同一类型的帽子。
限制条件：1<=n<=10例子：
The first line contains the value of n, next n lines contain collections
of all the n persons.
Input:
3
5 100 1 // Collection of the first person.
2 // Collection of the second person.
5 100 // Collection of the third person.
Output:
4
Explanation: All valid possible ways are (5, 2, 100), (100, 2, 5),
(1, 2, 5) and (1, 2, 100)
因为，方法的数量可能很大，所以输出模为100000007
我们强烈建议您尽量减少浏览器，并先自己尝试。 A. 简单解决方案 就是尝试所有可能的组合。首先从第一个集合中拾取第一个元素，将其标记为已访问，并对其余集合重复。它基本上是一个基于回溯的解决方案。
A. 更好的解决方案是使用比特屏蔽和DP .让我们首先介绍比特屏蔽。
什么是比特屏蔽？ 假设我们有一个从1到N的元素集合。如果我们想表示这个集合的一个子集，那么它可以由N位序列编码（我们通常称这个序列为“掩码”）。在我们选择的子集中，当且仅当掩码的第i位被设置，即它等于1时，第i个元素才属于它。例如，掩码10000101意味着集合[1…8]的子集由元素1、3和8组成。我们知道，对于一组N个元素，总共有2个 N 子集2 N 可以使用遮罩，每个遮罩代表一个子集。实际上，每个掩码都是一个用二进制表示法写的整数。
我们的主要方法是为每个掩码（以及每个子集）分配一个值，从而使用已经计算的掩码的值来计算新掩码的值。通常，我们的主要目标是计算完整集合的值/解，即掩模11111。通常，为了找到子集X的值，我们以各种可能的方式移除一个元素，并使用获得的子集X’的值 1. ，X’ 2. …，X’ K 计算X的值/解。这意味着X的值 我 必须已经计算过了，所以我们需要建立一个顺序，在这个顺序中将考虑遮罩。很容易看出，自然顺序会起作用：按相应数字的递增顺序检查遮罩。此外，我们有时从空子集X开始，以各种可能的方式添加元素，并使用获得的子集X’的值 1. ，X’ 2. …，X’ K 计算X的值/解。
我们主要在口罩上使用以下符号/操作： 位（i，掩码）–掩码的第i位 计数（掩码）–掩码中非零位的数量 第一位（掩码）–掩码中最低非零位的数目 设置（i，掩码）–设置掩码中的第i位 检查（i，掩码）-检查掩码中的第i位
如何使用比特屏蔽+DP解决这个问题？ 我们的想法是利用最多有10人的事实。所以我们可以使用一个整数变量作为位掩码来存储哪些人戴着帽子，哪些人不戴。
Let i be the current cap number (caps from 1 to i-1 are already
processed). Let integer variable mask indicates that the persons w
earing and not wearing caps. If i'th bit is set in mask, then
i'th person is wearing a cap, else not.
// consider the case when ith cap is not included
// in the arrangement
countWays(mask, i) = countWays(mask, i+1) +
// when ith cap is included in the arrangement
// so, assign this cap to all possible persons
// one by one and recur for remaining persons.
∑ countWays(mask | (1 << j), i+1)
for every person j that can wear cap i
Note that the expression "mask | (1 << j)" sets j'th bit in mask.
And a person can wear cap i if it is there in the person's cap list
provided as input.
如果我们画出完整的递归树，我们可以观察到许多子问题一次又一次地被解决。所以我们使用动态规划。使用表dp[][]以便在每个条目dp[i][j]中，i是掩码，j是帽号。
因为我们想要访问所有可以戴给定帽子的人，所以我们使用了一个向量数组，capList[101]。值capList[i]表示可以戴cap i的人员列表。
下面是上述想法的实现。
C/C++
// C++ program to find number of ways to wear hats #include<bits/stdc++.h> #define MOD 1000000007 using namespace std; // capList[i]'th vector contains the list of persons having a cap with id i // id is between 1 to 100 so we declared an array of 101 vectors as indexing // starts from 0. vector< int > capList[101]; // dp[2^10][101] .. in dp[i][j], i denotes the mask i.e., it tells that // how many and which persons are wearing cap. j denotes the first j caps // used. So, dp[i][j] tells the number ways we assign j caps to mask i // such that none of them wears the same cap int dp[1025][101]; // This is used for base case, it has all the N bits set // so, it tells whether all N persons are wearing a cap. int allmask; // Mask is the set of persons, i is cap-id (OR the // number of caps processed starting from first cap). long long int countWaysUtil( int mask, int i) { // If all persons are wearing a cap so we // are done and this is one way so return 1 if (mask == allmask) return 1; // If not everyone is wearing a cap and also there are no more // caps left to process, so there is no way, thus return 0; if (i > 100) return 0; // If we already have solved this subproblem, return the answer. if (dp[mask][i] != -1) return dp[mask][i]; // Ways, when we don't include this cap in our arrangement // or solution set. long long int ways = countWaysUtil(mask, i+1); // size is the total number of persons having cap with id i. int size = capList[i].size(); // So, assign one by one ith cap to all the possible persons // and recur for remaining caps. for ( int j = 0; j < size; j++) { // if person capList[i][j] is already wearing a cap so continue as // we cannot assign him this cap if (mask & (1 << capList[i][j])) continue ; // Else assign him this cap and recur for remaining caps with // new updated mask vector else ways += countWaysUtil(mask | (1 << capList[i][j]), i+1); ways %= MOD; } // Save the result and return it. return dp[mask][i] = ways; } // Reads n lines from standard input for current test case void countWays( int n) { //----------- READ INPUT -------------------------- string temp, str; int x; getline(cin, str); // to get rid of newline character for ( int i=0; i<n; i++) { getline(cin, str); stringstream ss(str); // while there are words in the streamobject ss while (ss >> temp) { stringstream s; s << temp; s >> x; // add the ith person in the list of cap if with id x capList[x].push_back(i); } } //---------------------------------------------------- // All mask is used to check whether all persons // are included or not, set all n bits as 1 allmask = (1 << n) - 1; // Initialize all entries in dp as -1 memset (dp, -1, sizeof dp); // Call recursive function count ways cout << countWaysUtil(0, 1) << endl; } // Driver Program int main() { int n; // number of persons in every test case cin >> n; countWays(n); return 0; } |
JAVA
// Java program to find number of ways to wear hats import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Vector; class Test { static final int MOD = 1000000007 ; // for input static BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); // capList[i]'th vector contains the list of persons having a cap with id i // id is between 1 to 100 so we declared an array of 101 vectors as indexing // starts from 0. static Vector<Integer> capList[] = new Vector[ 101 ]; // dp[2^10][101] .. in dp[i][j], i denotes the mask i.e., it tells that // how many and which persons are wearing cap. j denotes the first j caps // used. So, dp[i][j] tells the number ways we assign j caps to mask i // such that none of them wears the same cap static int dp[][] = new int [ 1025 ][ 101 ]; // This is used for base case, it has all the N bits set // so, it tells whether all N persons are wearing a cap. static int allmask; // Mask is the set of persons, i is cap-id (OR the // number of caps processed starting from first cap). static long countWaysUtil( int mask, int i) { // If all persons are wearing a cap so we // are done and this is one way so return 1 if (mask == allmask) return 1 ; // If not everyone is wearing a cap and also there are no more // caps left to process, so there is no way, thus return 0; if (i > 100 ) return 0 ; // If we already have solved this subproblem, return the answer. if (dp[mask][i] != - 1 ) return dp[mask][i]; // Ways, when we don't include this cap in our arrangement // or solution set. long ways = countWaysUtil(mask, i+ 1 ); // size is the total number of persons having cap with id i. int size = capList[i].size(); // So, assign one by one ith cap to all the possible persons // and recur for remaining caps. for ( int j = 0 ; j < size; j++) { // if person capList[i][j] is already wearing a cap so continue as // we cannot assign him this cap if ((mask & ( 1 << capList[i].get(j))) != 0 ) continue ; // Else assign him this cap and recur for remaining caps with // new updated mask vector else ways += countWaysUtil(mask | ( 1 << capList[i].get(j)), i+ 1 ); ways %= MOD; } // Save the result and return it. return dp[mask][i] = ( int ) ways; } // Reads n lines from standard input for current test case static void countWays( int n) throws Exception { //----------- READ INPUT -------------------------- String str; String split[]; int x; for ( int i= 0 ; i<n; i++) { str = br.readLine(); split = str.split( " " ); // while there are words in the split[] for ( int j = 0 ; j < split.length; j++) { // add the ith person in the list of cap if with id x x = Integer.parseInt(split[j]); capList[x].add(i); } } //---------------------------------------------------- // All mask is used to check of all persons // are included or not, set all n bits as 1 allmask = ( 1 << n) - 1 ; // Initialize all entries in dp as -1 for ( int [] is : dp) { for ( int i = 0 ; i < is.length; i++) { is[i] = - 1 ; } } // Call recursive function count ways System.out.println(countWaysUtil( 0 , 1 )); } // Driver method public static void main(String args[]) throws Exception { int n; // number of persons in every test case // initializing vector array for ( int i = 0 ; i < capList.length; i++) capList[i] = new Vector<>(); n = Integer.parseInt(br.readLine()); countWays(n); } } // This code is contributed by Gaurav Miglani |
python
#Python program to find number of ways to wear hats from collections import defaultdict class AssignCap: # Initialize variables def __init__( self ): self .allmask = 0 self .total_caps = 100 self .caps = defaultdict( list ) # Mask is the set of persons, i is the current cap number. def countWaysUtil( self ,dp, mask, cap_no): # If all persons are wearing a cap so we # are done and this is one way so return 1 if mask = = self .allmask: return 1 # If not everyone is wearing a cap and also there are no more # caps left to process, so there is no way, thus return 0; if cap_no > self .total_caps: return 0 # If we have already solved this subproblem, return the answer. if dp[mask][cap_no]! = - 1 : return dp[mask][cap_no] # Ways, when we don't include this cap in our arrangement # or solution set ways = self .countWaysUtil(dp, mask, cap_no + 1 ) # assign ith cap one by one to all the possible persons # and recur for remaining caps. if cap_no in self .caps: for ppl in self .caps[cap_no]: # if person 'ppl' is already wearing a cap then continue if mask & ( 1 << ppl) : continue # Else assign him this cap and recur for remaining caps with # new updated mask vector ways + = self .countWaysUtil(dp, mask | ( 1 << ppl), cap_no + 1 ) ways = ways % ( 10 * * 9 + 7 ) # Save the result and return it dp[mask][cap_no] = ways return dp[mask][cap_no] def countWays( self ,N): # Reads n lines from standard input for current test case # create dictionary for cap. cap[i] = list of person having # cap no i for ppl in range (N): cap_possessed_by_person = map ( int , raw_input ().strip().split()) for i in cap_possessed_by_person: self .caps[i].append(ppl) # allmask is used to check if all persons # are included or not, set all n bits as 1 self .allmask = ( 1 << N) - 1 # Initialize all entries in dp as -1 dp = [[ - 1 for j in range ( self .total_caps + 1 )] for i in range ( 2 * * N)] # Call recursive function countWaysUtil # result will be in dp[0][1] print self .countWaysUtil(dp, 0 , 1 ,) #Driver Program def main(): No_of_people = input () # number of persons in every test case AssignCap().countWays(No_of_people) if __name__ = = '__main__' : main() # This code is contributed by Neelam Yadav |
3 5 100 1 2 5 100
输出：
4
本文由Gaurav Ahirwar撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.cppku.com/wp-content/themes/zibll/img/thumbnail.svg)
