4
$\begingroup$

I have an MxN matrix where each element contains a positive numeric value.

I need to find those elements in the matrix that add up to the "maximum value". The caveat is that each row and column can be used at most once in calculating the total.

I have a brute force algorithm for doing this bit it's ugly. I was wondering if there is a well-known algorithm for accomplishing this.

$\endgroup$
7
$\begingroup$

Your problem is known as maximum weighted bipartite matching or the assignment problem, and has efficient algorithms such as the Hungarian algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.