Problem Link - Assign .This problem is known as assignment problem.
I read few solutions Here is one and they are trying to solve it using Bit-masking and DP .I tried and thought hard to understand how to solve it but i was unsuccessful ..
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityProblem Link - Assign .This problem is known as assignment problem.
I read few solutions Here is one and they are trying to solve it using Bit-masking and DP .I tried and thought hard to understand how to solve it but i was unsuccessful ..
Let us enumerate the students $s_1, \dots, v_n$. Let $A$ be the set of students and $B$ the set of subjects. Moreover, let $S_i$ be the set of subjects the student $s_i$ likes. The dynamic programming table will be $C\left(A, 2^B\right)$, where $C(s_i, S)$ says in how many ways we can assign the subjects in $S$ to the first $i$ students. Note that if $|S| \neq i$ we have $C(s_i, S) = 0$.
The recursive function is given by the formula $$C(s_i, S_i) = \sum_{p \in S \bigcap S_i} C(s_{i-1}, S\setminus {p}).$$
To implement the solution you need a loop over all the students and for each student iterate over all possible bit masks. For the student $i$ ignore all bitmasks with number of ones not equal to $i$. Now use the formula above to compute the value for each student and bitmask based on the values of previous students.
Notes: