adding numbers in permutations...

[Zwolf2190]

I am given a 2D array of ints need to find the maximum number generated when adding only one number from each col/row at a time.
EXAMPLE:
_ A B C
D 4 6 5
E 6 5 9
F 4 5 3

The possible outcomes are:
M1 S
A+D 4
B+E 5
C+F 3
Total 12

M2 S
A+D 4
B+F 5
C+E 9
Total 18

M3 S
A+E 6
B+D 6
C+F 3
Total 15

M4 S
A+E 6
B+F 5
C+D 5
Total 16

M5 S
A+F 4
B+D 6
C+E 9
Total 19

M6 S
A+F 4
B+E 5
C+D 5
Total 14

In this case, the best outcome would be M5 with a total of 19. I was given code for permutation of a word, but that's for characters in a 1D array. I'm having trouble editing the code to make it work for 2D integer arrays.
Thanks in advance!

[Zwolf2190]

My post, it's so lonely... Any thoughts?

[JLBorges]

Google 'linear assignment problem' and 'the hungarian method'

[Zwolf2190]

Thanks, that helped! The code on the internet for that is above my level of programming knowledge, but I understand it a little better. I'm working on getting the swap to work so i can easily do the permutations.

[JLBorges]

This is one way (recursion) to generate all possible combinations. The algorithm is obviously NP - O( N! )

#include <limits>

template< std::size_t N >
int max_sum( const int (&matrix) [N][N], std::size_t start_row,
              bool (&available_columns)[N] )
{
   if( start_row >= N ) return 0 ;

   const int (&row)[N] = matrix[start_row] ;
   int max_value = std::numeric_limits<int>::min() ;

   for( std::size_t i = 0 ; i < N ; ++i )
   {
       if( available_columns[i] )
       {
          available_columns[i] = false ;
          int sum = row[i] + max_sum( matrix, start_row+1, available_columns ) ;
          if( sum > max_value ) max_value = sum ;
          available_columns[i] = true ;
       }
   }

   return max_value ;
}

#include <iostream>

int main()
{
    enum { N = 3 } ;
    const int matrix[N][N] = { {4,6,5}, {6,5,9}, {4,5,3} } ;
    bool available[N] = { true, true, true } ;

    std::cout << max_sum( matrix, 0, available ) << '\n' ;
}