The largest amount per square matrix

Question

Given a square matrix of size nxn, where each cell is represented by a positive integer formula, find a list of n integers from this matrix that their sum is as large as possible, but not two integers appear in the same row or column in the original matrix.

So my best idea was that since we know that choosing a cell to be added to the sum means that all the cells in the same row and column can no longer get there, we can calculate the “cost ", this cell has. Since the sum of the rows is the same for each cell in the row, we can ignore our calculations. Formally:

for each cell in each row:
    if (columnNotYetVisited AND (-1 * sumOfTheColumn) + (2 * valueOfTheCell) > currentMax):
        currentMax = (-1 * sumOfTheColumn) + (2 * valueOfTheCell);

if endOftheRow:
    mark columnWithBestCost as visited;
    add currentMax to finalSum;

And although it works for some inputs, there are some where it fails by a wide margin. What is the best approach for this problem?

EDIT: Also, the test test that I have on me now, in case it comes in handy:

7   53  183 439
627 343 773 959
447 283 463 29
217 623 3   399

Edited   OUT: 2282 (439 + 773 + 447 + 623)

Answer 1

I decided to use dynamic programming and bitmask

//                 bitmask      
int F(int stage, int selecion)
{
  if(stage == N) return selecion == (1<<N)-1 ? 0 : -INF;

  if(dp[stage][selecion] != -1)
    return dp[stage][selecion];

  int answer = -INF;

  for(int i = 0;i < N;i++)
    if((selecion & (1 << i)) == 0) 
        answer = max(answer, matrix[i][stage] + F(stage+1, selecion | (1 << i) ) );

  dp[stage][selecion] = answer;

  return answer;
}

here is all my code

I think this can be solved with other algorithms like hungarian , but it works well for a small matrix (20x20)

, spoj ( , 0)