vaibnak7's blog

Maximizing the number of toys taken
By vaibnak7, history, 5 years ago, In English

I recently came across the following question.

Given a matrix representing which child likes which toy. matrix[i][j]=1 represents that child i likes toy j. One child can get only 1 toy and one toy can be assigned to only 1 child.Find maximum number of children who can get the toy they wished.

One approach i can think of is going through all possible ways of distributing the toys but it wont work if the constraints are high, what can be a better approach.

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem can be solved by computing the maximum flow in the graph(you can use Dinic's algorithm). You should create a graph with n (children) + m (toys) + 2 (source and sink), edges from each child to each toy, which he want to get. The capacity of each edge should be 1. And now you should just find the maximum flow.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the constraints are small like the matrix is 20 by 20 we can use dp + bit masking. Refer to this problem to gain some idea about dp + bit masking. https://www.spoj.com/problems/ASSIGN/

Here is the code:

int n;
int memo[1<<20][20];
int matrix[20][20];
int dp(int mask, int i)
{
  if(memo[mask][i] != -1)
        return memo[mask][i];

  int ans = 0;
  for(int j = 0; j < n; j++)
    if( !(mask&(1<<j)) )//not set
        ans = max(ans, matrix[i][j] + dp(mask|(1<<j), i+1));
  return memo[mask][i] = ans;
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> matrix[i][j];
    for(int i = 0; i < (1<<n); i++)
        for(int j = 0; j < n; j++)
            memo[i][j] = -1;
    cout << dp(0, 0);
}
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

This is known as maximum matching in a bipartite graph and can be solved using Hopcroft Karp

→ Reply