CODEWITHSUNDEEP
c#algorithmdynamic-programming
user1234524521
user1234524521

Reputation: 97

Choose one element from each row and column in matrix and the sum is minimized

If you have a NxN matrix of positive integers, and you are asked to select exactly one element from each row and column, so that the sum of the selected elements is minimized, how can it be solved?

I think it is about Dynamic Programming. I have tried to minimize the time O(n!) using memoization:

    Dictionary<byte[,], int>[] memo = new Dictionary<byte[,], int>[17];

    int rec(byte[,] arr)
    {
        if (arr.Length == 1) return arr[0, 0];
        int opt = find(arr);
        if (opt != -1) return opt;
        opt = 1 << 25;
        for (int i = 0; i < arr.GetLength(1); ++i)
            opt = Math.Min(opt, arr[0, i] + rec(divide(arr, i)));
        add(arr, opt);
        return opt;
    }

This chooses an element from row 0 of the current matrix and then divides the matrix and calls itself recursively to solve the submatrix. Function divide divides the current matrix according to the selected element. The sub-matrix size is then (N-1)x(N-1). Function find performs linear search in memo[n], and add adds the solution to memo[n] But this is too slow as it will compare each matrix with other.

Do you have some inhancements? Is there a faster DP algorithm? Any help is appreciated

EXAMPLE

1     2     3    4

8     7     6    5

9     11    10   12

13    14    16   15

The optimal solution: 1 + 5 + 10 + 14

Steps:

7   6  5

11 10 12

14 16 15

11 10

14 16

14

Upvotes: 4

Views: 3816

Answers (1)

tmyklebu
tmyklebu

Reputation: 14205

This is actually the assignment problem. It can be solved in polynomial time using the Hungarian algorithm, among other methods.

Upvotes: 4

Related Questions