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.

advertisement

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

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.

Expected Input and Output

Case-1:

advertisement
 
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:

 
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.

advertisement
  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.

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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn