algorithm - 行数和列数相等的矩阵

Question

我有 NxM 矩阵，其整数元素大于或等于 0。

我可以从任何单元格将 1 传输到另一个单元格(-1 到源单元格，+1 到目标单元格)。使用此操作，我必须使所有行和列的总和相等。问题是如何找到最少的此类操作来完成我的任务。在处理过程中，细胞可能是阴性的。

例如，对于

1 1 2 2

1 0 1 1

0 0 1 1

1 1 1 2

答案是3。

P.s.: 我试过自己解决，但只能用暴力解决。

Answer 1

首先，找到每行和每列的预期总和¹。

rowSum = totalSum / numRows
colSum = totalSum / numCols

然后，遍历行和列并计算以下值:

rowDelta = 0
for each row r
    if sum(r) > rowSum
       rowDelta += sum(r) - rowSum

colDelta = 0
for each col c
    if sum(c) > colSum
       colDelta += sum(c) - colSum

平衡所有行和列的最小移动数是:

minMoves = max(rowDelta, colDelta)

这是可行的，因为您必须从超过 rowSum 的行转移到不超过它的行，以及从超过 colSum 的列转移到不超过它的列超越它。

如果最初 rowDelta 低于 colDelta，那么您将达到平衡所有行但列仍未平衡的阶段。在这种情况下，您将继续从单元格转移到同一行中的其他单元格。如果最初 colDelta 低于 rowDelta，这同样适用，这就是我们选择它们之间的最大值作为预期结果的原因。

_{¹ 如果 totalSum 不是 numRows 或 numCols 的倍数，那么问题有无解。}