This is a C++ Program that Solves the Assignments Problem using Dynamic Programming technique.
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).
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.
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.
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:
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
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.
#include<bits/stdc++.h>
using namespace std;
long long int assign(int n, vector<vector<int> > preference)
{
int mx=1<<n;
int i,j;
int s;
/*
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.
*/
vector<long long int> dp(mx,0);
dp[mx-1]=1;
//proceed in bottom up manner
for(int mask=mx-1;mask>=0;mask--)
{
//now find the student
j=mask;
s=0;
//count no. of set bits in mask
while(j)
{
s+=(j&1);
j/=2;
}
//so, this is a state for student s
for(i=0;i<n;i++)
{
if(preference[s][i] && !(mask & (1<<i)))
{
dp[mask]+=dp[mask | (1<<i)];
}
}
}
//this is the result
return dp[0];
}
int main()
{
int i,n,j;
cout<<"How many students are there ? "<<endl;
cin>>n;
vector<vector<int> > preference(n+1,vector<int>(n,0));
cout<<endl<<"Enter the preferences of each of "<<n<<" students for "<<n<<" subjects"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>preference[i][j];
}
}
cout<<endl<<"Total number of assignments that can be prepared are "<<endl;
cout<<assign(n,preference)<<endl;
return 0;
}
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.
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.
- Check Programming Books
- Practice Programming MCQs
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Data Structure Books