Loopin's blog

By Loopin, history, 8 years ago, In English

You have nXn matrix filled with numbers,you have to pick n numbers from it such that their sum is maximal and no 2 are in same column or row. My guesses after 20 mins: I tried greedy algorithm,sorting each row and memorizing column of each number in new sorted matrix and now I would take largest in each row and if 2 are in same column I would pick larger and move pointer for row of lower one to next largest number,but no can do,found counterexample,we can pick lower one if number behind greater number is much larger then number behind lower number...

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's assignment problem. https://en.wikipedia.org/wiki/Assignment_problem It can be solved with flows or hungarian alrogithm.