Блог пользователя Loopin

Автор Loopin, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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