4

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

1 回答 1

3

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

于 2012-12-25T23:21:04.287 回答