Flip, найти максимальную сумму матрицы путем умножения линий и столбиков на Опции

[DarkWishmaster]

Привет. Вот интересная задача:
Дана матрица NxM где её элементы положитнльные и отрицательные числа. Можно умножить сколько раз угодно любую линию и любой столбик на -1. Найдите максимальную суму чисел из матрицы которая может получиться путем этих умножений.
Например:
5 3
4 -2 2
3 -1 5
2 0 -3
4 1 -3
5 -3 2
Умножаем 3 линию и 2 столбик. Сума=28.
Есть идеи как это вообще сделать?
Сначала я думал что можно пройтись по линиям и столбикам и если по модулю сума отрицательных чисел больше положительных то умножаем на -1, но такой способ не помогает так как когда мы умножаем линию то изменются и колоны и наоборот.

[IUnknown]

овсем забыл: 1<=N,M<=18,

В таком случае подобный моему метод решения вполне допустим. Надо только изменить типы с Integer на Longint...

Обьясните пожалуйста вот эту строку:

Давай я лучше объясню сам алгоритм сначала? Итак. Решение основано на полном переборе всех возможных вариантов: каждая из строк может либо умножаться на (-1), либо нет. То же самое касается и столбцов. Поэтому делаем цикл от 0 до 2^{число_строк} - 1 и в нем проверяем все возможные комбинации. То есть, при N = 3 цикл будет от 0 до 2³ - 1, т.е., 0 .. 7. Запиши эти значения в двоичном виде - получишь:

000
001
010
011
100
101
110
111
Т.е., все возможные комбинации. Здесь бит, равный 0 означает, что со строкой ничего делать не надо, а равный 1 - что ее надо изменить. Как изменить - понятно, домножить на (-1). Теперь делаем вложенный цикл, которые делает то же самое со столбцами, и считаем для каждого варианта сумму всех элементов матрицы...

Теперь по поводу строки

minusi := 1 - 2 * ((rows shr i) and $1);

Здесь minusi будет равно 1, если Rows в i-том бите справа содержит 0 (то есть, строку номер i изменять не надо), и -1, если i-ый бит Rows установлен в 1. То есть, этой строкой я просто напросто вытаскиваю нужный бит из проверяемого в данный момент варианта Rows (с Cols то же самое), а потом домножаю элемент матрицы на (minusi * minusj) при суммировании... Так учитываются все изменения строк/столбцов без фактического изменения элементов матрицы...

Ещё это $1. Я так понял если (rows shr i) четно то выдает 0 иначе 1.

Правильно понял. Но ведь (rows shr i) будет четно только тогда, когда бит номер i равен 0, иначе (если бит единичный) оно нечетно... А если отнять от 1-цы удвоенное значение ((rows shr i) and $1), то получишь 1, если бит был сброшен (поскольку 1 - 2 * 0 = 1), и (-1), если бит был установлен (поскольку 1 - 2 * 1 = -1)... Вот такая небольшая хитрость

Сообщение отредактировано: IUnknown - 5.07.2011 12:18

[DarkWishmaster]

IUnknown,
Надеюсь я понял:
первые два цикла перебирают абсолютно все комбинации столбцов и линий в двоичной системе, а последнее два считывают суму этого варианта. Супер! Самое интересное что матрицу это никак не изменяют.


Сообщение отредактировано: DarkWishmaster - 5.07.2011 12:41