4
$\begingroup$

I have a table like this:

    a    b    c    d    e    f A   2.3  4.2  1.1  2.0  7.7  0.8 B   2.2  1.0  4.4  4.3  4.5  4.4 C   1.2  1.2  3.2  3.4  4.3  4.3 D   1.8  8.1  2.3  2.6  2.5  2.0 

From A to D are places, from a to f are people. Each number means the "distance" of the corresponding people from place. For example, from A to a is 2.3 units long.

Now I want 4 of the people to choose a place to go. No one goes to more than one place and no place should have more than one people, (but 2 of the people are not going,) so that the total distance is the minimum possible.

For example, If A-a, B-b, C-c and D-d, you get 2.3 + 1.0 + 3.2 + 2.6 = 8.1. But if you make it A-c, B-b, C-a and D-f, you'll get 1.1 + 1.0 + 1.2 + 2.0 = 5.3 which is better.

I want a algorithm than can be programmed to find the best plan. Is there any algorithm for this?

  • 1
    Google "maximum weighted bipartite matching"2011-09-11

3 Answers 3