title: Maximize sum of table where each number must come from unique row and column
body: <p>Suppose we have a table of numbers like this (we can assume it is a square table):</p>
  
  <pre><code>20  2   1   3   4
  5   1   14  8   9
  15  12  17  17  11
  16  1   1   15  18
  20  13  15  5   11
  </code></pre>
  
  <p>Your job is to calculate the maximum sum of n numbers where n is the number of rows or columns in the table. The catch is <strong>each number must come from a unique row and column.</strong> </p>
  
  <p>For example, selecting the numbers at (0,0), (1,1), (2,2), (3,3), and (4,4) is acceptable, but (0,0), (0,1), (2,2), (3,3), and (4,4) is not because the first two numbers were pulled from the same row.</p>
  
  <p>My (laughable) solution to this problem is iterating through all the possible permutations of the rows and columns. This works for small grids but, of course, it is incredibly slow as n gets big. It has O(n!) time complexity, if I'm not mistaken (sample Python code below).</p>
  
  <p>I really think this can be solved in better time, but I'm not coming up with anything sufficiently clever.</p>
  
  <p>So my question is, what algorithm should be used to solve this?</p>
  
  <p>If it helps, this problem <em>seems</em> similar to the 
  <a href="http://en.wikipedia.org/wiki/List_of_knapsack_problems">knapsack problem</a>.</p>
  
  <pre><code>import itertools
  import re
  
  grid = """20    2   1   3   4
  5   1   14  8   9
  15  12  17  17  11
  16  1   1   15  18
  20  13  15  5   11"""
  grid = [[int(x) for x in re.split("\s+", line)] for line in grid.split("\n")]
  
  possible_column_indexes = itertools.permutations(range(len(grid)))
  max_sum = 0
  max_positions = []
  for column_indexes in possible_column_indexes:
      current_sum = 0
      current_positions = []
      for row, col in enumerate(column_indexes):
          current_sum += grid[row][col]
          current_positions.append("(%d, %d)" % (row, col))
      if current_sum &gt; max_sum:
          max_sum = current_sum
          max_positions = current_positions
  
  print "Max sum is", max_sum
  for position in max_positions:
      print position
  </code></pre>