c# - 从矩阵的每一行和每一列中选择一个元素，求和最小化

Question

如果你有一个 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

Answer 1

这实际上是assignment problem .可以使用 Hungarian algorithm, 在多项式时间内求解以及其他方法。