Assignments Problem – Dynamic Programming Solutions

This is a C++ Program that Solves the Assignments Problem using Dynamic Programming technique.

Problem Description

Your task will be to calculate number of different assignments of n different topics to n students such that everybody gets exactly one topic he likes.

First line of input contains number of students n.

Each of the next n lines contains n integers describing preferences of one student. 1 at the ith position means that this student likes ith topic, 0 means that he definitely doesn’t want to take it.

For each test case output number of different assignments (it will fit in a signed 64-bit integer).

Problem Solution

This is a bitmask DP problem. The first step of a DP problem is to define a state.

State(k, bitmask) = the number of ways of assigning assignments to students k .. N, with bitmask representing the assignments that are already assigned to students 1 .. k-1.

advertisement
advertisement

Then the recursive formula for this state is,

State(k, bitmask) = sum { State(k+1, bitmask with bit i switched ON if student k likes assignment i) }

This recursive formula is implemented by creating an array dp[] for memoization.
student=no. of bits set in integer i
dp[i] = the number of ways of assigning assignments to students s .. n
If jth bit of integer i is set, it means that the subject j is already assigned to students 1 .. s-1 and it cannot be assigned to student s.

We will calculate the values in Bottom up manner by first finding dp[(2^n)-1], then dp[(2^n)-2] and so on.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Expected Input and Output

Case-1:

 
No. of students = 3
preference matrix = 1 1 1
                    1 1 1
                    1 1 1
 
Expected result= 6

Case-2:

 
No. of students = 6
preference matrix = 1 1 1 0 1 0
                    0 1 0 1 0 1
                    1 0 1 0 1 0
                    0 0 1 1 0 1
                    1 1 1 0 1 1
                    1 1 1 1 1 1
 
Expected result= 68

Case-3:

advertisement
 
No. of students = 3
preference matrix = 1 0 0 1 0 0 0 0 0 1 1 
                    1 1 1 1 1 0 1 0 1 0 0 
                    1 0 0 1 0 0 1 1 0 1 0 
                    1 0 1 1 1 0 1 1 0 1 1 
                    0 1 1 1 0 1 0 0 1 1 1 
                    1 1 1 0 0 1 0 0 0 0 0 
                    0 0 0 0 1 0 1 0 0 0 1 
                    1 0 1 1 0 0 0 0 0 0 1 
                    0 0 1 0 1 1 0 0 0 1 1 
                    1 1 1 0 0 0 1 0 1 0 1 
                    1 0 0 0 1 1 1 1 0 0 0 
 
Expected result=7588
Program/Source Code

Here is source code of the C++ Program for Assignments problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. long long int assign(int n, vector<vector<int> > preference)
  6. {
  7.     int mx=1<<n;
  8.     int i,j;
  9.     int s;
  10.  
  11.     /*
  12.        student=no. of bits set in integer i 
  13.        dp[i] = the number of ways of assigning assignments to students s .. n 
  14.       
  15.        If jth bit of integer i is set, it means that the subject j is  already assigned to students 1 .. s-1 and it cannot be assigned to student s.
  16.  
  17.     */
  18.  
  19.     vector<long long int> dp(mx,0);
  20.     dp[mx-1]=1;
  21.  
  22.     //proceed in bottom up manner
  23.     for(int mask=mx-1;mask>=0;mask--)
  24.     {
  25.         //now find the student
  26.         j=mask;
  27.         s=0;
  28.  
  29.         //count no. of set bits in mask
  30.         while(j)
  31.         {
  32.             s+=(j&1);
  33.             j/=2;
  34.         }
  35.  
  36.         //so, this is a state for student s
  37.         for(i=0;i<n;i++)
  38.         {
  39.             if(preference[s][i] && !(mask & (1<<i)))
  40.             {
  41.                 dp[mask]+=dp[mask | (1<<i)];
  42.             }
  43.         }
  44.     }
  45.  
  46.     //this is the result
  47.     return dp[0];
  48. }
  49.  
  50. int main()
  51. {
  52.     int i,n,j;
  53.  
  54.     cout<<"How many students are there ? "<<endl;
  55.     cin>>n;
  56.  
  57.     vector<vector<int> > preference(n+1,vector<int>(n,0));
  58.  
  59.     cout<<endl<<"Enter the preferences of each of "<<n<<" students for "<<n<<" subjects"<<endl;
  60.  
  61.     for(i=0;i<n;i++)
  62.     {
  63.         for(j=0;j<n;j++)
  64.         {
  65.             cin>>preference[i][j];
  66.         }
  67.     }
  68.  
  69.     cout<<endl<<"Total number of assignments that can be prepared are "<<endl;
  70.     cout<<assign(n,preference)<<endl;
  71.  
  72.  
  73.     return 0;
  74. }
Program Explanation

In the main function, we take the number of students and preferences of all student (in the form of matrix) as input. Then, function origin is invoked with the input as parameters.

In the function origin, the preference matrix is processed and result is returned. The result is displayed.

advertisement
Runtime Test Cases
 
Case-1:
$ g++ assignment.cpp
$ ./a.out
How many students are there ? 
3
 
Enter the preferences of each of 3 students for 3 subjects
1 1 1
1 1 1
1 1 1
 
Total number of assignments that can be prepared are 
6
 
Case-2:
$ ./a.out
How many students are there ? 
6
 
Enter the preferences of each of 6 students for 6 subjects
1 1 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 0 1 1 0 1
1 1 1 0 1 1
1 1 1 1 1 1
 
Total number of assignments that can be prepared are 
68
 
Case-3:
$ ./a.out
How many students are there ? 
11
 
Enter the preferences of each of 11 students for 11 subjects
1 0 0 1 0 0 0 0 0 1 1 
1 1 1 1 1 0 1 0 1 0 0 
1 0 0 1 0 0 1 1 0 1 0 
1 0 1 1 1 0 1 1 0 1 1 
0 1 1 1 0 1 0 0 1 1 1 
1 1 1 0 0 1 0 0 0 0 0 
0 0 0 0 1 0 1 0 0 0 1 
1 0 1 1 0 0 0 0 0 0 1 
0 0 1 0 1 1 0 0 0 1 1 
1 1 1 0 0 0 1 0 1 0 1 
1 0 0 0 1 1 1 1 0 0 0 
 
Total number of assignments that can be prepared are 
7588

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.