Best way to get the highest sum from a Matrix (using Java but algorithm is the issue here)

Question

Sorry I dont know the correct terminology to use but I have a 3x3 matrix like this

1 3 4 
5 4 5  
2 2 5  

and I want get the highest score by picking a value from each row/column but I cant pick the same row or column more than once , so the answer in this case is

3 + 5 + 5 = 13 (row0,col1 + row1,col0 + row2,col2)

4 + 5 + 5 = 14 is not allowed because would have picked two values from col2

I'm using Java, and typically the matrix would be 15 by 15 in size.

Is there a name for what Im trying to do, and whats the algorithm

thanks Paul

EDIT:Note:the hungarian algorithm only works when no of rows equals no of cols, and in my case this is not always the case I regularly have cases of 10x12 or 11x13. But it appears you can get round this by adding extra dummy rows.

EDIT hmm, trying out one of these implmentations and it doesnt alwasy seem to work, unless Im misreading it

100.0,100.0,100.0,100.0,30.0,80.0,80.0,100.0,100.0,80.0,
80.0,100.0,100.0,100.0,80.0,80.0,25.0,100.0,100.0,80.0,
80.0,100.0,100.0,100.0,80.0,25.0,80.0,100.0,100.0,80.0,
100.0,25.0,80.0,100.0,100.0,100.0,100.0,100.0,100.0,100.0,
0.0,100.0,100.0,100.0,100.0,80.0,80.0,100.0,100.0,100.0,
100.0,100.0,100.0,100.0,100.0,100.0,100.0,100.0,25.0,100.0,
100.0,100.0,100.0,25.0,100.0,100.0,100.0,75.0,100.0,100.0,
100.0,80.0,30.0,100.0,75.0,100.0,100.0,100.0,100.0,100.0,
100.0,100.0,100.0,100.0,80.0,80.0,80.0,100.0,100.0,25.0,
100.0,100.0,100.0,75.0,100.0,100.0,100.0,25.0,100.0,100.0,
Results calculated
0:4,0,
1:3,1,
2:7,2,
3:6,3,
4:0,4,
5:2,5,
6:1,6,
7:9,7,
8:5,8,
9:8,9,

Answer 1

It's the assignment problem. You can look at the rows as "people" and the columns as "assignments". You want to minimise (well, you want to maximise but the idea remains) the total cost, where each person can do one task for matrix[i][j] money.

The hungarian algorithm is a good solution, but it is fairly complicated. I think bruteforcing it will work just fine on 15x15 matrices.