We're facing following problem - an n * n 2D Matrix contains doubles (Java). Find a Set of elements such that Each element in the set comes from a unique row and column combination. That is, once you've selected an element (i, j) as a candidate for a set, that set cannot contain any elements from ith row or jth column.The size of the set is Maximized. The Matrix may contain NaNs, so it may not be possible to find a set of size n.The sum of elements on this set is minimum over all sets of this size for this Matrix.For Example, consider following matrix -1 2 3 44 1 2 33 4 1 22 3 4 1This is artificially constructed to demonstrate the problem, solution for this Matrix is going to be the diagonal elements {1, 1, 1, 1}Any ideas?Just to be sure, this is not a homework problem. We're trying to solve this for a client. Problem we're trying to solve is in Transport domain, and basically boils  down to problem statement above.I've tried to think of a polytime solution, but the first condition seems to be problematic. If it was not in place, this would have been a trivial DP problem - create a temporary 2d array, traverse each row of original array, and for each element, try to find element in last row in temporary array that has the smallest cumulative sum. Make this element's value in temp_arr smallest cumulative sum + this element. Find smallest element in last row and you're done.I'm trying to see if there is a polynomial time solution. In all probability, it will be easier to code, verify, and debug than any graph theory based solutions.Edit added after some search - Just realized that what I was looking for was Hungarian Algorithm for Assignment problem - https://en.wikipedia.org/wiki/Hungarian_algorithm
Select a set of elements from a 2D matrix, such that each element comes from distinct row and column
algorithms;graphs;arrays
This is maximum matching in a weighted bipartite graph in disguise. (You can easily convert your objective of minimizing the sum of weights into one of maximizing it.)