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]

перебор по какому параметру? )

По всем вариантам от 0 до (2^N - 1) и от 0 до (2^M - 1), разумеется. Если бы ТС указал, какие значения могут принимать M, N - может быть этот вариант и не родился бы. А так - для не очень больших значений он вполне работоспособен:

Если M, N могут быть большими, сюда можно даже не смотреть (Показать/Скрыть)

const
   N = 5; // rows
   M = 3; // cols

   A : array[0 .. Pred(N), 0 .. Pred(M)] of integer =
   (
      (4, -2,  2),
      (3, -1,  5),
      (2,  0, -3),
      (4,  1, -3),
      (5, -3,  2)
   );

var
   rows, i, cols, j : integer;
   s, max : longint;
   minusi, minusj : integer;

begin
   max := -maxlongint;
   writeln(max);
   for rows := 0 to Pred (1 shl N) do
   begin
      for cols := 0 to Pred(1 shl M) do
      begin
         s := 0;
         for i := 0 to Pred(N) do
         begin
            for j := 0 to Pred(M) do
            begin
               minusi := 1 - 2 * ((rows shr i) and $1);
               minusj := 1 - 2 * ((cols shr j) and $1);
               s := s + A[i, j] * minusi * minusj;
            end;
         end;
         writeln('i = ', i, 'j = ', j, ' s = ', s);
         if s > max then max := s;
      end;
   end;
   writeln(max);
end.

Прекрасно находит эту самую сумму = 28...