Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
Your problem is known as maximum weighted bipartite matching or the assignment problem, and has efficient algorithms such as the Hungarian algorithm.
