Матрица с равной суммой строк и столбцов

Question

У меня есть матрица NxM с целочисленными элементами, большими или равными 0.

Из любой ячейки я могу перевести 1 в другую (-1 в исходную ячейку, +1 в пункт назначения). Используя эту операцию, я должен сделать суммы для всех строк и столбцов равными. Вопрос в том, как найти минимальное количество таких операций для достижения моей задачи. Во время обработки ячейки могут быть отрицательными.

Например, для

1 1 2 2

1 0 1 1

0 0 1 1

1 1 1 2

Ответ 3.

Пс .: Я пытался решить ее самостоятельно, но пришел только к решению проблемы грубой силы.

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, то проблема не имеет решения.}

Answer 2

Давайте рассмотрим одномерный случай: у вас есть массив чисел, и вам разрешена одна операция: возьмите 1 из значения одного из элементов массива и добавьте его к другому элементу. Цель состоит в том, чтобы сделать все элементы равными с минимальными операциями. Здесь решение простое: вы выбираете случайное «слишком большое число» и добавляете одно к случайному «слишком маленькому» числу. Позвольте мне теперь описать, как это связано с рассматриваемой проблемой.

Вы можете легко рассчитать сумму, которая необходима для каждого столбца и каждой строки. Это общая сумма всех элементов в матрице, деленная на количество столбцов или строк соответственно. С этого момента вы можете рассчитать, какие строки и столбцы нужно уменьшить, а какие - увеличить. смотри здесь:

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).

Однако я докажу, что исходная задача может быть решена ровно за столько же шагов, сколько и максимальное количество шагов, необходимых для решения задачи для столбцов и строк:

Каждый шаг в более простой задаче генерирует два индекса i и j: индекс, из которого нужно вычесть, и индекс, к которому нужно добавить. Предположим, что в шаге задачи столбца у нас есть индексы ci и cj, а в задаче строки у нас есть индексы ri и rj. Затем мы назначаем соответствие этому в первоначальном задании: возьмите 1 из (ci, ri) и добавьте одно к (cj, rj). В определенный момент мы столкнемся с ситуацией, в которой может быть еще больше шагов, скажем, в задаче столбцов, а не в задаче строк. Таким образом, мы получаем ci и cj, но что мы делаем для ri и rj? Мы просто выбираем ri = rj, чтобы не путать вычисления строк.

В этом решении я использую тот факт, что мне разрешено получать отрицательные числа в матрице.

Теперь давайте продемонстрируем:

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)

Answer 3

Supose thar r1 - это индекс строки с максимальной суммой, а r2 - строка с минимальной суммой. c1 столбец с максимальной суммой и c2 столбец с минимальной.

Вам необходимо повторить следующую операцию:

1. если Matrix[r1][c1] == Matrix[r2][c2] мы закончили!
2. В противном случае, Matrix[r1][c1] -= 1 и Matrix[r2][c2] += 1