3

给定一个N x N矩阵,其中N <= 25和每个单元格都有一个正整数值,您如何将其划分为最多 K 行(直线上/下线或直线左/右线 [注意:它们必须从一侧延伸到其他])以便最大值组(由分区确定)最小?

例如,给定以下矩阵

1 1 2
1 1 2 
2 2 4

并且我们可以使用 2 行来划分它,我们应该在第 2 列和第 3 列之间画一条线,以及在第 2 和第 3 行之间画一条线,它给出了最小化的最大值 4。

我的第一个想法是用一个位掩码来表示每行的状态,用 2 个整数来表示它。但是,这太慢了。我认为复杂性是O(2^(2N))也许你可以为行解决它,然后为列解决它?

有人有想法么?

编辑:这是我用谷歌搜索后的问题:http ://www.sciencedirect.com/science/article/pii/0166218X94001546

另一篇论文:http ://cis.poly.edu/suel/papers/pxp.pdf

我试着读那个^

4

1 回答 1

0

您可以尝试垂直线的所有子集,然后对水平线进行动态规划。

假设您已将垂直线集固定为 S。将包含固定垂直线集 S 的矩阵的前 K 行的子问题的答案表示为 D(K, S)。然后找到一个递归来解决具有较小子问题的 D(K, S) 是微不足道的。

如果您在开始时预先计算每个子矩阵的大小,则总体复杂度应为 O(2^N * N^2)。

于 2013-02-25T14:34:56.103 回答