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

Автор Lakh, история, 4 года назад, По-английски

Given an array of size N*N (1<=N<=1000) . We can select only one element from each row. Once an element is selected from a given row the column containing that element is freezed. Now for further rows we can't select any element from that column. The problem is to minimize the sum of selected elements .

I am thinking of some dp approach but size of N seems a bit large. Please suggest any other way to solve this problem. Thanks.

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

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

I think the fastest way is O(N^3) using the Hungarian Algorithm unless the array has some other special property