Interesting Matrix problem

Правка en1, от 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...

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Loopin 2017-02-13 22:53:06 4
en1 Английский Loopin 2017-02-13 22:50:41 592 Initial revision (published)