Finding the maximum sum from a matrix

There is a matrix with m rows and n columns. The task is to find the maximum sum choosing a single element from each row and column. I came up with a solution, which finds the maximum from the whole matrix and then sets that row and column as zero adds it to the sum and proceeds with finding the next max. This repeats m times.

开发者_C百科

But the problem with this approach was if there is repetitive elements. I'll try to explain it with an example. Here is the matrix..

3 6 5 3

9 4 9 2

8 1 4 3

4 7 2 5

Now, if I follow the above method.. sum will be 9 + 7 + 5 + 3 whereas it should be 9 + 8 + 7 + 3. How to solve this problem.. I'm stuck

Update: The columns are cost of seats which can be assigned to a person and the rows are number of persons. We want to assign them in such a way, so that we get the max cost.

---

Isn't this just http://en.wikipedia.org/wiki/Assignment_problem, typically solved by http://en.wikipedia.org/wiki/Hungarian_algorithm? Obviously, you want a maximum rather than a minimum, but surely you can achieve that by maximising for costs that are -(the real cost) or, if you are worried about -ve costs, (Max cost in matrix) - (real cost).

---

Your algorithm is wrong - consider a slight change in the matrix, where the second 9 is 8:

3 6 5 3 
9 4 8 2 
8 1 4 3 
4 7 2 5 

Then your algorithm has no problem in finding 9, 7, 5, 3 (no duplicates), but the correct answer is still 8, 8, 7, 3.

You can brute force it, by trying all combinations. One good way to put that into code is to use a recursive function, that solves the problem for any matrix:

In it you would iterate through say the first row and call the function for the submatrix obtained by deleting the correspondent row and column. Then you would pick the highest sum.

That, of course, will be too slow for large matrixes. The complexity is O(N!).