求最佳x指数的算法，使每个象限中的点和最小。

Question

我有一个包含各种数据点的2D数组。参考图1，我需要把它分成4个象限，这样每个象限内的所有点的和都被最小化了。每个象限的最小大小是4x4，它可以大但不小，它不一定是一个正方形。例如，最优象限的大小可以是5x3。

​

​

我需要找到最优指数x和y，这将导致象限，其中最小和。

我看到的是重量分配问题。我可以把所有的值加到我的2D数组中，得到和，S，现在，我需要在4个象限上大致相等地分配这个和S。我知道我已经提到，每个象限的和必须是最小可能，但它更像是平衡最小。

Answer 1

您可以使用总和面积表有效地对每个象限中的值进行求和。这是一个矩阵，其维数与矩阵相同，其中table[i][j]是原始矩阵中从0行到i行和0到j列之间的所有元素的总和。

您可以这样计算它(伪代码)：

for i = 0 to rows
    row_sum = 0
    for j = 0 to columns
        row_sum += matrix[i][j]
        table[i][j] = row_sum
        if i > 0
            table[i][j] += table[i-1][j]

上面的代码在每一行中保持运行和，并将其添加到同一列上一行的表项中。

然后，您可以使用这个表来计算给定分割的每个象限的值。假设您想要在第一行之后水平划分为象限，在第j列之后垂直分割成象限，象限如下所示：

a | b
--+--
c | d

你可以像这样计算象限和：

a = table[i][j]
b = table[i][columns-1] - a
c = table[rows-1][j] - a
d = table[rows-1][columns-1] - (a + b + c)

因此，您可以迭代矩阵，并计算每个可能的分裂位置的象限和使用4个表查找和一些简单的加减。跟踪最优(根据你的标准，例如最小象限和最大值之间的最小差)，这就是你的答案。

它是矩阵中元素数的O(n)。