Considere la siguiente declaración de problemas.
Hay 100 tipos diferentes de gorras, cada una con una identificación única del 1 al 100. Además, hay ‘n’ personas, cada una con una colección de un número variable de gorras. Un día todas estas personas deciden ir a una fiesta con gorra pero para lucir únicas decidieron que ninguna usaría el mismo tipo de gorra. Entonces, cuente el número total de arreglos o formas de modo que ninguno de ellos use el mismo tipo de gorra.
Restricciones: 1 <= n <= 10 Ejemplo:
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)
Dado que la cantidad de formas podría ser grande, el módulo de salida es 1000000007
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Una solución simple es probar todas las combinaciones posibles. Comience eligiendo el primer elemento del primer conjunto, márquelo como visitado y repítalo para los conjuntos restantes. Es básicamente una solución basada en Backtracking.
Una mejor solución es utilizar Bitmasking y DP . Primero introduzcamos Bitmasking.
¿Qué es el enmascaramiento de bits?
Supongamos que tenemos una colección de elementos que están numerados del 1 al N. Si queremos representar un subconjunto de este conjunto, entonces puede codificarse mediante una secuencia de N bits (generalmente llamamos a esta secuencia una «máscara»). En nuestro subconjunto elegido, el i-ésimo elemento le pertenece si y solo si el i-ésimo bit de la máscara está activado, es decir, es igual a 1. Por ejemplo, la máscara 10000101 significa que el subconjunto del conjunto [1… 8 ] consta de los elementos 1, 3 y 8. Sabemos que para un conjunto de N elementos hay un total de 2 N subconjuntos, por lo que son posibles 2 N máscaras, una que representa cada subconjunto. Cada máscara es, de hecho, un número entero escrito en notación binaria.
Nuestra metodología principal es asignar un valor a cada máscara (y, por lo tanto, a cada subconjunto) y así calcular los valores de las máscaras nuevas utilizando los valores de las máscaras ya calculadas. Por lo general, nuestro objetivo principal es calcular el valor/solución para el conjunto completo, es decir, para la máscara 11111111. Normalmente, para encontrar el valor de un subconjunto X, eliminamos un elemento de todas las formas posibles y usamos valores para los subconjuntos obtenidos X’ 1 , X ‘ 2 … ,X’ k para calcular el valor/solución de X. Esto significa que los valores de X’ i ya debe haberse calculado, por lo que debemos establecer un orden en el que se considerarán las máscaras. Es fácil ver que el orden natural funcionará: repasar las máscaras en orden creciente de los números correspondientes. Además, a veces comenzamos con el subconjunto vacío X y agregamos elementos de todas las formas posibles y usamos los valores de los subconjuntos obtenidos X’ 1 , X’ 2 … ,X’ k para calcular el valor/solución para X.
Principalmente usamos las siguientes notaciones/operaciones en las máscaras:
bit(i, máscara) – el i-ésimo bit de la máscara
contar(máscara) – el número de bits distintos de cero en la máscara
primero(máscara) – el número del más bajo bit distinto de cero en el
conjunto de máscaras (i, máscara) – establezca el i-ésimo bit en la
comprobación de máscara (i, máscara) – verifique el i-ésimo bit en la máscara
¿Cómo se resuelve este problema usando Bitmasking + DP?
La idea es aprovechar el hecho de que hay hasta 10 personas. Entonces podemos usar una variable entera como una máscara de bits para almacenar qué persona está usando una gorra y cuál no.
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.
Si dibujamos el árbol de recursión completo, podemos observar que muchos subproblemas se resuelven una y otra vez. Entonces usamos Programación Dinámica. Se utiliza una tabla dp[][] de modo que en cada entrada dp[i][j], i es la máscara y j es el número de tapa.
Dado que queremos acceder a todas las personas que pueden usar una gorra determinada, usamos una array de vectores, capList[101]. Un valor capList[i] indica la lista de personas que pueden usar gorra i.
A continuación se muestra la implementación de la idea anterior.
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
Aporte:
3 5 100 1 2 5 100
Producción:
4
Este artículo es una contribución de Gaurav Ahirwar. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA