算法帮助 : divide a matrix to N continuous cells, 具有接近相等的项目总和

Question

我有一个具有 R 行和 C 列的整数矩阵 A。
我想实现一个函数f(mat A, uint N)将矩阵分成连续的N个单元格，所有的单元格一起覆盖整个矩阵区域，比如每个单元格中的项目之和单元格 i1 ... iN 尽可能接近相等。
到目前为止，我从一个简单、昂贵的实现开始，它首先从 N/2 x N/2 简单网格开始，计算每个单元格的总和，然后迭代调整网格线。
显然，它在运行时既不是最优解也不是最优解，并且也仅限于与其他单元格共享水平和垂直限制的矩形单元格。

请问我该如何解决这个问题？(我目前的解决方案产生类似的东西:

---------------------------
|        |          |     |
---------------------------
|        |          |     |
|        |          |     |
---------------------------
|        |          |     |
---------------------------

或

---------------------------
|       | |               |
|       | |               |
|       | |               |
---------------------------
|       | |               |
|       | |               |
---------------------------
|       | |               |
---------------------------

)

我希望细节清楚，如果有任何需要澄清的地方，请告诉我。

谢谢!

Answer 1

要部分回答问题，请注意您描述的问题包含 Partition problem作为子问题，即 NP-complete ;因此，您问题中的问题也是NP-complete这使得存在高效算法的可能性很小。