Нужен алгоритм, чтобы все строки и столбцы имели неотрицательные суммы

Question

Я пытаюсь выяснить эту проблему.У меня есть матрица с целочисленными значениями.Цель состоит в том, чтобы получить так, чтобы каждая сумма строки и каждая сумма столбца была неотрицательной.Единственное, что я могу сделать, это изменить знаки целого ряда или целого столбца.

Вот что я пробовал.Я ищу строку или столбец с отрицательной суммой и переворачиваю ее.Это работает на всех примерах, которые я пробовал, но теперь я должен объяснить, почему, и я не уверен.Иногда, когда я делаю это, количество отрицательных сумм увеличивается, например, когда я переворачиваю строку, иногда появляются и другие плохие столбцы.Но я не могу найти пример, где это не работает, и я не знаю, как еще решить проблему.

Answer 1

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

Проблема в том, что вам не нужно отслеживать, сколько строк или столбцов нужно перевернуть, а какова сумма всех записей. Пусть A будет матрицей, а a будет суммой всех записей. Когда вы переворачиваете строку или столбец с помощью суммы -s (s положительно), это добавляет 2 к a. Поскольку a ограничено сверху, в конечном итоге этот процесс должен завершиться.

Answer 2

Предположим, у вас есть строка целых чисел, a, b, c ... и т. Д.

Если a + b + c + ... = n, то переключая все знаки, вы получаете

(- a) + (-b) + (-c) + (-) ... = - (a + b + c + ...) = -n

Если n отрицательно, то -n положительно, поэтому вы только что сделали строку положительной, перевернув все знаки. Это математика вашего метода, по крайней мере.

Это то, что вы ищете?