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, но такой способ не помогает так как когда мы умножаем линию то изменются и колоны и наоборот.

[sheka]

Можно выбрать только одну строку и одинстолбец?

[DarkWishmaster]

Можно выбрать только одну строку и одинстолбец?

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

[Krjuger]

Самый простой вариант сделать полный перебор)))Но производительность будет аховая....
Насамом деле я думаю,если внести в твою идею некоторые корректировки,то что то путное выйдет.Смотри у тебя есть 2 варианта,либо ты умножаеш строку либо столбец.Как варант,ты находиш максимальную сууму в строке,Если надо изменить всю строку,то ты меняеш и ничего не делаеш со столбцами,если чтобы достигнуть максимума тебе в строке надо изменить 1 или 2 элемента(я отталкиваюсь от твоей матрици),то ты совершаеш эти действия для подматрицы без первой строки и дальше смотриш,если разница сумм исходной и измененной подматриц больше нуля,то ты применяеш изменения для исходной матрици,если меньше нуля,то сравниваеш это число и тем,на сколько больше нам удалось получить от изменени в первой строке,если все таки первая строка нам позволит увеличить сумму то применяеш,если нет,то отменяеш изменения и переходиш на 2 строку и все аналогично.

Больше пока что ничего в голову не лезет.Задача явно переборная и надо максимально сократить этот перебор.У моего варианта достаточно много минусов,постараюсь придумать вариант получше.

[Lapp]

Самый простой вариант сделать полный перебор)))Но производительность будет аховая.... <...> Задача явно переборная и надо максимально сократить этот перебор.У моего варианта достаточно много минусов,постараюсь придумать вариант получше.

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

[Unconnected]

Перебирать тут наверное оочень долго можно.. может, запомнить самые потенциально интересные строки\столбцы (где по модулю отриц. больше), и в каждом переборе от них плясать (заканчивать тогда, когда полезную инверсию сделать уже нельзя)?

[Lapp]

DarkWishmaster, ограничения на размеры матрицы накладываются?

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

[DarkWishmaster]

DarkWishmaster, ограничения на размеры матрицы накладываются?

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

Добавлено через 15 мин.

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

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

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

Ещё это $1. Я так понял если (rows shr i) четно то выдает 0 иначе 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 16:18

[DarkWishmaster]

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


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

[TarasBer]

Я тут подумал немного.

1. Если разешить переворачивать только столбцы, то задача становится тривиальной - надо просто перевернуть все столбцы с отрицательной суммой.

2. Мы можем для каждой комбинации переворотов строк применить задачу из п.1. Таким образом, время сокращается с O(2^(n+m)) до O((2^n) *m*n).

Что ещё можно сделать, я пока не знаю.

[DarkWishmaster]

IUknown,
Вообщем твое решение дает 20 баллов из 100 ( там тесты онлайн я их не видел ), нашел одно решение (100/100), вроде он тут только по столбикам идет. Эту строку пока не пойму:

 if i and (1 shl (j-1))>0

 Program p1;
var  a : array[1..100,1..100] of longint;
n,m,max : longint;

 
 
Procedure ReaData;
var fin : text;
i,j : integer;
begin
assign(fin,'flip.in');
reset(fin);
readln(fin,n,m);
for i:=1 to n do
for j:=1 to m do
read(fin,a[i,j]);
close(fin);
end;
 
 
Procedure CheckMax;
var s,i,j,t,k : longint;
fout : text;
 begin
    for i:=1 to (1 shl m) do
        begin
           s:=0;
           for k:=1 to n do
              begin
                 t:=0;
                 for j:=1 to m do
                 if i and (1 shl (j-1))>0 then t:=t-a[k,j] else
                 t:=t+a[k,j];
                 if t<-t then s:=s-t else s:=s+t;
              end;
          if s>max then max:=s;
        end;
assign(fout,'flip.out');
rewrite(fout);
writeln(fout,max);
close(fout);
end;
 
begin
ReadData;
CheckMax;
end.

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

[TarasBer]

Опа, стобальное решение как моё.

> Эту строку пока не пойму:
> if i and (1 shl (j-1))>0

Означает "если j-1-ый бит в числе i ненулевой".
Вот ты два раза подряд просишь объяснить одинаковую строку.
Сначала прочитай http://ru.wikipedia.org/wiki/Битовые_операции

[IUnknown]

нашел одно решение (100/100), вроде он тут только по столбикам идет.

Вот и спрашивай у автора этого решения. Я в чужом копаться не собираюсь. Мне интереснее свое написать...

Кстати, если тебе надо онлайн-тесты проходить - это надо заранее указывать, я вообще бы к таким задачам не прикасался. Мало того, что решает один, а сдает - другой, так еще и не пойми какие ограничения, и по размеру, и по времени... Короче, зря написал код... Больше не повторится...

[TarasBer]

Если бы в онлайн-тестах хотя бы примерно указывалось, почему программа не прошла тест (типа "в тесте был случай нулевого кол-ва элементов"), то это было бы нормально.

А пока что я понимаю Вольво: онлайн-тесты больше похожи на

- У меня не работает твоя программа, почини!
- А что вы с ней делали?
- Не работает программа, я же сказал!
- А какие данные примерно вы в неё забивали?
- Тебе что, ещё раз повторить - твоя программа не работает?

Чини то, не знаю что - это как-то глупо и неэффективно.

[Unconnected]

Чини то, не знаю что - это как-то глупо и неэффективно.

С другой стороны, учит находить острые углы в коде, на которых может не всё работать.. хотя тяжко конечно, когда на 1 из 50 тестов ошибка, и сидишь втыкаешь, что может быть)

[TarasBer]

> С другой стороны, учит находить острые углы в коде

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