Minimize task cost with only two workers

I'm trying to create an algorithm, using PHP, that would figure out best way to complete a set of tasks by choosing two workers that can complete those tasks as cheaply as possible.

Suppose that I have a set of X different tasks and Y different workers. Each worker can complete each of the X tasks for a different price. You can assume that I have a table showing, for each worker and each task, the price that worker requires to comp开发者_Python百科lete the task.

My question is this: given such a table, how would I find the set of exactly two workers who could complete all of the tasks for the least total cost?

A very simple approach to solving this problem would be to consider all possible pairs of two workers and then to compute the cost if those two workers were to divide up all the work optimally. Once you had those values, you could just take the smallest of all of them to get the overall smallest cost.

Now, let's see how to compute the total cost of completing all X tasks if you were to use a particular pair of workers. From your problem description it doesn't seem like each worker has a limit as to how much they can do, which makes this substantially easier than many related problems. The intuition is this: for any task, you want to give that task to the worker that can do it cheaper than the other. Consequently, the total cost of divvying up all the tasks between the two workers can be found by looping over every task, then assigning that task to the worker who can do it for less money.

Overall, I would suggest approaching this problem as follows. Using a double for loop, iterate across every pair of workers. For each pair, use a third for loop to iterate over every task, computing the total cost of completing that task. Finally, if this pair is better than the best known pair so far, update your guess to be this particular pair. Once you've run this loop over every pair of workers, you'll have found the pair that can do it for the least total price.

Since there are O(Y²) pairs of workers and X total tasks, this will complete in O(Y²X) time.

Hope this helps!

This is an optimization problem that can be solved using dynamic programming methods. Your particular problem (I believe) falls under the category of resource allocation with financial constraints. Standard problems like the knapsack problem are included in there as well.

There is at least one question on stack overflow asking for solutions to such problems using php. In that post there's a link to a php solution for the knapsack problem. I'd start from that code and morph it into what you need to get a handle on your particular problem definition.