Last Updated: 17 Apr, 2022
Ninja And The Clan
Moderate
Asked in company
There are ‘N’ Ninjas in a clan and the clan leader wants to assign ‘N’ tasks to each of the Ninjas. There is a ‘cost’ matrix of size ‘N’ x ‘N’, where ‘COST[i][j]’ denotes the cost of ‘i’th Ninja completing the ‘j’th task. The leader wants to assign the task in such a way that the total cost is minimized.
Note that each task is assigned to a single Ninja, and each Ninja will only be allotted a single task.
EXAMPLE:
Input:
'N' = 3
‘COST’ = [[1 2 3],
[6 5 6],
[3 8 9]]
Output: 11
A possible assignment is:
Assign task 1 to ninja 3, task 2 to ninja 1 and task 3 to ninja 2, total cost = 3 + 2 + 6 = 11
Input Format :
The first line will contain the integer 'T', the number of test cases. For each test case
The first line of each test case an integer ‘N’ denoting the number of Ninjas and tasks.
The next ‘N’ lines contain ‘N’ integers denoting the cost of ith Ninja completing the jth task.
Output format :
For each test case, print a single integer denoting the minimum cost of the assignment.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= 'T' <= 10
1 <= 'N' <= 18
1 <= 'COST[i][j]' <= 10^5
Time Limit: 1 sec
Approaches
Approach:
We can generate all permutations of task assignments and for each assignment calculate the cost.
Find the minimum overall (N!) assignments
Algorithm :
- Create and initialize an array ‘ASSIGNMENT’ of size ‘N’ to store the current assignment of the task.
- Initialize a ‘RES’ variable as ‘0’.
- Run a for loop from i = 0 to n
- Set task ‘i’ to person ‘i’
- For each next lexicographically greater permutation :
- Create a ‘TOTALCOST’ variable to store the cost of the permutation.
- Run a for loop from i = 0 to ‘N’
- Add COST[i][ASSIGNMENT[i]] to ‘TOTALCOST’.
- ‘RES’ = min(RES, TOTALCOST)
- return ‘RES’
Approach:
- Since 'N' is limited to 10, we can represent the assigned task using a bitmask (0 for not assigned and 1 for assigned). We can have up to 2^10 masks ~= 1024.
- The idea is to assign some tasks to some group of people and then using this assignment calculate the best answer for not assigned people.
- We store each state of an assignment as a bitmask or a number.
- Suppose the state of ‘DP’ is (K, mask), where K represents that persons from 0 to K - 1 have been assigned a task, and ‘mask’ is a binary number, whose ith bit represents if the ith task has been assigned or not.
- Now, suppose we have answer(K, mask), we can assign a task i to person K, if ith task is not yet assigned to any person i.e. mask & (1 << i ) = 0 then, answer(K + 1, mask| ( 1 << i ) will be given as :
answer(K + 1, mask| (1<<i) = min ( answer(K + 1, mask | (1<<i) , answer(K, mask) + cost[k][I]
One thing to note here is that ‘K’ is always equal to the number set bits in ‘mask’, so we can remove that. So the ‘DP’ state now is just (mask), and if we have the answer(mask), then
answer(mask | (1<<i )) = min( answer(mask | (1<<i)), answer(mask) + cost[x][i] )
Here X = the number of set bits in ‘mask’.
Algorithm :
- Initialize the ‘DP’ array of size ‘2^N’ with ‘INFINITY’.
- Set base condition as, DP[0] = 0
- Run a for loop from mask = 0 to ‘2^N’
- Initialize a variable ‘X’ as number of set bits in ‘mask’
- Run a for loop from j = 0 to ‘N’
- Check if jth bit is not set in i
- DP[mask | (1<<j)] = min(DP[mask|(1<<j)], DP[mask] + cost[x][j])
- Check if jth bit is not set in i
- Return ‘DP[2^N - 1]’