Interesting Matrix problem

Revision en1, by Loopin, 2017-02-13 22:50:41

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...

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Loopin 2017-02-13 22:53:06 4
en1 English Loopin 2017-02-13 22:50:41 592 Initial revision (published)