optimization - Hungarian algorithm with multiple assignments -

let's we're given n jobs , k workers jobs. jobs need 2 employees, while need one. employees can't jobs. example worker 1 can jobs 1,2 , 5, while not jobs 3 , 4. if hire worker 1 job 1, want him jobs 2 , 5, since we've paid him.

so example let's have 5 jobs , 6 workers. jobs 1,2 , 4 need 2 men, while jobs 3 , 5 need one. , here's list of jobs every worker can , wage requires.

worker 1 can jobs 1,3,5 , requires 1000 dollars.  worker 2 can jobs 1,5 , requires 2000 dollars.  worker 3 can jobs 1,2 , requires 1500 dollars.  worker 4 can jobs 2,4 , requires 2500 dollars.  worker 5 can jobs 4,5 , requires 1500 dollars.  worker 6 can jobs 3,5 , requires 1000 dollars.  

after little calculation , logical thinking can conclude have hire workers 1,3,4 , 5, means minimum wage need pay is: 1000+1500+2500+1500=5500 dollars.

but how can find efficient algorithm output amount? somehow reminds me of hungarian algorithm, additional constrains makes impossible me apply it.

we can represent state of jobs number in ternary system(2-two people remaing, 1-one person remaining , 0 if done). can compute f(mask, k) = smallest cost hire workers among first k in such way state of remaining jobs mask. transitions follows: either go (mask, k + 1)(not hiring current worker) or go (new_mask, k + 1)(in case pay worker salary , let him jobs can). answer f(0, k).

the time complexity o(3^n * k * n).

here idea how optimize further(and rid of n factor). let's assume current mask mask , man can jobs mask'. add mask mask', there 1 problem: positions there 2 in mask , 1 in mask' broken. can fix: each mask, let's precompute binary mask allowed_mask contain position digit not 2. each man , each allowed_mask can precompute mask' value. each transition 1 addition:

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

note there 2^n allowed masks. time complexity of solution o(3^n * n + t * 2^n * k * n + t * 3^n * k)(the first term precomputing allowed_masks ternary mask, second 1 precomputing mask' allowed_masks , people, , last dp itself).