Привет. Вот интересная задача: Дана матрица NxM где её элементы положитнльные и отрицательные числа. Можно умножить сколько раз угодно любую линию и любой столбик на -1. Найдите максимальную суму чисел из матрицы которая может получиться путем этих умножений. Например: 5 3 4 -2 2 3 -1 5 2 0 -3 4 1 -3 5 -3 2 Умножаем 3 линию и 2 столбик. Сума=28. Есть идеи как это вообще сделать? Сначала я думал что можно пройтись по линиям и столбикам и если по модулю сума отрицательных чисел больше положительных то умножаем на -1, но такой способ не помогает так как когда мы умножаем линию то изменются и колоны и наоборот.
sheka
4.07.2011 23:54
Можно выбрать только одну строку и одинстолбец?
DarkWishmaster
5.07.2011 2:11
Цитата(sheka @ 4.07.2011 19:54)
Можно выбрать только одну строку и одинстолбец?
если бы, но можно сколько угодно столбцов и линий выбрать
Krjuger
5.07.2011 4:24
Самый простой вариант сделать полный перебор)))Но производительность будет аховая.... Насамом деле я думаю,если внести в твою идею некоторые корректировки,то что то путное выйдет.Смотри у тебя есть 2 варианта,либо ты умножаеш строку либо столбец.Как варант,ты находиш максимальную сууму в строке,Если надо изменить всю строку,то ты меняеш и ничего не делаеш со столбцами,если чтобы достигнуть максимума тебе в строке надо изменить 1 или 2 элемента(я отталкиваюсь от твоей матрици),то ты совершаеш эти действия для подматрицы без первой строки и дальше смотриш,если разница сумм исходной и измененной подматриц больше нуля,то ты применяеш изменения для исходной матрици,если меньше нуля,то сравниваеш это число и тем,на сколько больше нам удалось получить от изменени в первой строке,если все таки первая строка нам позволит увеличить сумму то применяеш,если нет,то отменяеш изменения и переходиш на 2 строку и все аналогично.
Больше пока что ничего в голову не лезет.Задача явно переборная и надо максимально сократить этот перебор.У моего варианта достаточно много минусов,постараюсь придумать вариант получше.
Lapp
5.07.2011 5:52
Цитата(Krjuger @ 5.07.2011 1:24)
Самый простой вариант сделать полный перебор)))Но производительность будет аховая.... <...> Задача явно переборная и надо максимально сократить этот перебор.У моего варианта достаточно много минусов,постараюсь придумать вариант получше.
Krjuger, перебор по какому параметру? )
Unconnected
5.07.2011 5:56
Перебирать тут наверное оочень долго можно.. может, запомнить самые потенциально интересные строки\столбцы (где по модулю отриц. больше), и в каждом переборе от них плясать (заканчивать тогда, когда полезную инверсию сделать уже нельзя)?
Lapp
5.07.2011 12:49
DarkWishmaster, ограничения на размеры матрицы накладываются?
IUnknown
5.07.2011 13:03
Цитата
перебор по какому параметру? )
По всем вариантам от 0 до (2N - 1) и от 0 до (2M - 1), разумеется. Если бы ТС указал, какие значения могут принимать M, N - может быть этот вариант и не родился бы. А так - для не очень больших значений он вполне работоспособен:
Если M, N могут быть большими, сюда можно даже не смотреть(Показать/Скрыть)
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
5.07.2011 15:39
Цитата(Lapp @ 5.07.2011 8:49)
DarkWishmaster, ограничения на размеры матрицы накладываются?
Ещё это $1. Я так понял если (rows shr i) четно то выдает 0 иначе 1.
IUnknown
5.07.2011 16:16
Цитата
овсем забыл: 1<=N,M<=18,
В таком случае подобный моему метод решения вполне допустим. Надо только изменить типы с Integer на Longint...
Цитата
Обьясните пожалуйста вот эту строку:
Давай я лучше объясню сам алгоритм сначала? Итак. Решение основано на полном переборе всех возможных вариантов: каждая из строк может либо умножаться на (-1), либо нет. То же самое касается и столбцов. Поэтому делаем цикл от 0 до 2число_строк - 1 и в нем проверяем все возможные комбинации. То есть, при N = 3 цикл будет от 0 до 23 - 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)... Вот такая небольшая хитрость
DarkWishmaster
5.07.2011 16:40
IUnknown, Надеюсь я понял: первые два цикла перебирают абсолютно все комбинации столбцов и линий в двоичной системе, а последнее два считывают суму этого варианта. Супер! Самое интересное что матрицу это никак не изменяют.
TarasBer
5.07.2011 16:57
Я тут подумал немного.
1. Если разешить переворачивать только столбцы, то задача становится тривиальной - надо просто перевернуть все столбцы с отрицательной суммой.
2. Мы можем для каждой комбинации переворотов строк применить задачу из п.1. Таким образом, время сокращается с O(2^(n+m)) до O((2^n) *m*n).
Что ещё можно сделать, я пока не знаю.
DarkWishmaster
5.07.2011 17:31
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.
TarasBer
5.07.2011 17:45
Опа, стобальное решение как моё.
> Эту строку пока не пойму: > if i and (1 shl (j-1))>0
нашел одно решение (100/100), вроде он тут только по столбикам идет.
Вот и спрашивай у автора этого решения. Я в чужом копаться не собираюсь. Мне интереснее свое написать...
Кстати, если тебе надо онлайн-тесты проходить - это надо заранее указывать, я вообще бы к таким задачам не прикасался. Мало того, что решает один, а сдает - другой, так еще и не пойми какие ограничения, и по размеру, и по времени... Короче, зря написал код... Больше не повторится...
TarasBer
5.07.2011 17:54
Если бы в онлайн-тестах хотя бы примерно указывалось, почему программа не прошла тест (типа "в тесте был случай нулевого кол-ва элементов"), то это было бы нормально.
А пока что я понимаю Вольво: онлайн-тесты больше похожи на
- У меня не работает твоя программа, почини! - А что вы с ней делали? - Не работает программа, я же сказал! - А какие данные примерно вы в неё забивали? - Тебе что, ещё раз повторить - твоя программа не работает?
Чини то, не знаю что - это как-то глупо и неэффективно.
Unconnected
5.07.2011 18:02
Цитата
Чини то, не знаю что - это как-то глупо и неэффективно.
С другой стороны, учит находить острые углы в коде, на которых может не всё работать.. хотя тяжко конечно, когда на 1 из 50 тестов ошибка, и сидишь втыкаешь, что может быть)
TarasBer
5.07.2011 18:05
> С другой стороны, учит находить острые углы в коде
Пальцем в небо тыкать это учит. Когда тебе прямо говорят, что глюк в таком-то месте на таких-то данных и ты сразу правишь, то это учит писать правильный код намного быстрее. Потому что не тратятся мозговые ресурсы на бесполезную в реальной жизни телепатическую работу.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.