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

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

**Related Posts:**

- Practice Design & Analysis of Algorithms MCQ
- Check Data Structure Books
- Check Computer Science Books
- Apply for Computer Science Internship
- Check Programming Books