给定一个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
我试着读那个^