Hungarian multi-task algorithm

Question

Let's say we were given N jobs and K jobs to complete these tasks. But for some jobs, we need 2 employees, while for some we need only one. Also, employees cannot complete all tasks. For example, employee 1 can complete tasks 1,2 and 5, rather than tasks 3 and 4. In addition, if we hire employee 1 to complete work 1, then we want him to complete tasks 2 and 5, since we already paid his.

So, let's say we have 5 jobs and 6 workers. For tasks 1,2 and 4 we need 2 people, and for jobs 3 and 5 we need only one. And here is a list of the jobs that every worker can do, and the wages he requires.

Worker 1 can do jobs 1,3,5 and he requires 1000 dollars. Worker 2 can do jobs 1,5 and he requires 2000 dollars. Worker 3 can do jobs 1,2 and he requires 1500 dollars. Worker 4 can do jobs 2,4 and he requires 2500 dollars. Worker 5 can do jobs 4,5 and he requires 1500 dollars. Worker 6 can do jobs 3,5 and he requires 1000 dollars. 

After a little calculation and logical thinking, we can conclude that we must hire workers 1,3,4 and 5, which means that the minimum wage that we have to pay is: 1000 + 1500 + 2500 + 1500 = $ 5500.

But how can we find an efficient algorithm that will output this amount? This somehow reminds me of the Hungarian algorithm, but all these additional restrictions do not allow me to apply it.

Answer 1

We can represent the state of all tasks as a number in the triple system (2-two people, reissue, 1st person and 0, if this has already been done). Now we can calculate f (mask, k) = the lowest cost in order to hire some workers among the first k so that the state of the remaining tasks is a mask. The transitions are as follows: we either go (mask, k + 1) (without hiring the current worker), or go to (new_mask, k + 1) (in this case, we pay this employee his salary and allow him to do all the jobs, which he can). Answer: f (0, K).

The complexity of time is O (3 ^ N * K * N).

Here is an idea how to optimize it further (and get rid of factor N ). Suppose that the current mask is mask , and a person can perform tasks from another mask' . We could just add mask to mask' , but there is one problem: the positions where there were 2 in mask and 1 in mask' will be broken. But we can fix it: for each mask, allow to precommute the allowed_mask binary mask, which contains the entire position where the number is not 2 . For each person and for each allowed_mask we can allowed_mask value of mask' . Now each transition is just one addition:

 for i = 0 ... k - 1 for mask = 0 ... 3^n - 1 allowed_mask = precomputed_allowed_mask[mask] // make a transition to (i + 1, mask + add_for_allowed_mask[i][allowed_mask]) // make a transition to (i + 1, mask) 

Note that there are only 2^n allowed masks. Thus, the time complexity of this solution is O(3^N * N + T * 2^N * K * N + T * 3^N * K) (the first term for the preliminary calculation of admissible masks for all ternary masks, the second for the preliminary mask' calculations for all allowed masks and people, and the latter for dp itself).