Lakh's blog

By Lakh, history, 4 years ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

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

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