矩阵的行和列的总和相等 [英] Matrix with equal sum of rows and columns

问题描述

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

I have NxM matrix with integer elements, greater or equal than 0.

从任何细胞可以传输1至另一个（-1到源小区，1到目的地）。 使用这个操作，我必须让资金用于所有的行和列相等。现在的问题是如何找到这样的操作的最低量，以实现我的任务。在该处理期间的细胞可以是负的。

From any cell I can transfer 1 to another one (-1 to the source cell, +1 to the destination). Using this operation, I have to make sums for all rows and columns equal. The question is how to find the minimal amount of such operations to achieve my task. During the processing cells may be negative.

例如，对

1 1 2 2

1 0 1 1

0 0 1 1

1 1 1 2

答案是3。

PS：我试图解决我自己的，但来到只有蛮力解决方案

P.s.: I've tried to solve it on my own, but came only to brute-force solution.

推荐答案

让我们考虑一维的情况：你有数字数组，你允许一个单一的操作：取1的元素之一的价值阵列并将其添加到其它元件。的目标是使等于以最小的操作的所有元素。在这里，解决方法很简单：你选择随机过大数字，并添加一个随机的太小号。现在让我介绍了如何这涉及到手头的问题。

Let us consider the one dimensional case: you have an array of numbers and you are allowed a single operation: take 1 from the value of one of the elements of the array and add it to other element. The goal is to make all elements equal with minimal operations. Here the solution is simple: you choose random "too big number" and add one to random "too small" number. Let me now describe how this relates to the problem at hand.

您可以轻松地计算出所需要的每一列，每一行的总和。这是在矩阵分别由列或行的数量除以所有元素的总和。从此可以计算哪些行和列需要降低并 - 增加。在这里看到：

You can easily calculate the sum that is needed for every column and every row. This is the total sum of all elements in the matrix divided by the number of columns or rows respectively. From then on you can calculate which rows and columns need to be reduced and which - increased. see here:

1 1 2 2 -2
1 0 1 1 +1
0 0 1 1 +2
1 1 1 2 -1
+1+2-1-2
Expected sum of a row: 4
Expected sum of a column: 4

所以，现在我们产生两个数组：位移行中的数组： -2，+ 1，+ 2，-1 和位移的列数： + 1，+ 2，-1，-2 。对于这两个阵列我们解决上述简单的任务。显而易见的是，我们不能解决在比所需的简单的任务的那些（否则在列或行的平衡也不会为0）的步骤更少的初始问题

So now we generate two arrays: the array of displacements in the rows: -2,+1,+2,-1 and the number of displacements in the columns: +1,+2,-1,-2. For this two arrays we solve the simpler task described above. It is obvious that we can not solve the initial problem in fewer steps than the ones required for the simpler task (otherwise the balance in the columns or rows will not be 0).

但是我会证明的初始任务可以作为是解决对于列和行的任务所需的步骤的最大来解决在完全一样的许多步骤进行：

However I will prove that the initial task can be solved in exactly as many steps as is the maximum of steps needed to solve the task for the columns and rows:

在简单的任务的每一步产生两个指数我和Ĵ：从该指数减去与指数要添加。在列的任务，我们有指数 CI 和 CJ 并在该行的任务，我们有索引的一步让我们假设里和 RJ 。然后，我们指定的这一个对应的初始任务：取1从（CI，RI）并添加一个（CJ，RJ）。在某一点，我们将达到在该行的任务的情况，其中有可能是，比如说还更步骤中，列任务并没有更多。所以，我们得到 CI 和 CJ ，但我们该怎么做了里和 RJ ？我们只是选择里 = RJ ，这样我们就不会搞砸了该行的计算。

Every step in the simpler task generates two indices i and j: the index from which to subtract and the index to which to add. Lets assume in a step in the column task we have indices ci and cj and in the row task we have indices ri and rj. Then we assign a correspondence of this in the initial task: take 1 from (ci, ri) and add one to (cj, rj). At certain point we will reach a situation in which there might be still more steps in, say, the columns task and no more in the rows task. So we get ci and cj, but what do we do for ri and rj? We just choose ri=rj so that we do not screw up the row calculations.

在此溶液我正在使用的我允许获得负数在基质中的事实。

In this solution I am making use of the fact I am allow to obtain negative numbers in the matrix.

现在可以证明：

Solution for columns:
4->1;3->2;4->2
Solution for rows:
1->3;1->3;2->4

Total solution:
(4,1)->(1,3);(3,1)->(2,3);(4,2)->(2,4)

这篇关于矩阵的行和列的总和相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！