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.

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:

 
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.

```
 
```
```
#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;
```
```
}
```

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.

« Prev - Bytelandian Gold Coins Problem – Dynamic Programming Solutions

» Next - Blueberries Problem – Dynamic Programming Solutions

Related Posts:

Recommended Articles: