从矩阵的每一行和每一列中选择一个元素，并将其和最小化

本文关键字：元素 一个 最小化 选择 一行 一列 | 更新日期: 2023-09-27 17:49:27

如果你有一个正整数的NxN矩阵，你被要求从每一行和每一列中选择一个元素，使所选元素的总和最小，如何解决这个问题?

我想是关于动态规划的。我已经尝试使用记忆最小化O(n!)的时间:

    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;
    }

从当前矩阵的第0行中选择一个元素，然后对矩阵进行除法并递归调用自身来求解子矩阵。函数divide根据所选元素对当前矩阵进行除法。子矩阵的大小为(N-1)x(N-1)。函数find在memo[n]中执行线性搜索，add将解添加到memo[n]中，但这太慢了，因为它会比较每个矩阵。

你有什么进步吗?有没有更快的DP算法?任何帮助都是感激的

1     2     3    4
8     7     6    5
9     11    10   12
13    14    16   15

最优解:1 + 5 + 10 + 14

步骤:

7   6  5
11 10 12
14 16 15

11 10
14 16

14

从矩阵的每一行和每一列中选择一个元素，并将其和最小化

这实际上是赋值问题。在其他方法中，它可以使用匈牙利算法在多项式时间内求解。

相关文章：