Flip, найти максимальную сумму матрицы путем умножения линий и столбиков на |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Flip, найти максимальную сумму матрицы путем умножения линий и столбиков на |
DarkWishmaster |
4.07.2011 19:40
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
Привет. Вот интересная задача:
Дана матрица 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 19:54
Сообщение
#2
|
Я. Группа: Пользователи Сообщений: 809 Пол: Мужской Реальное имя: Саша Репутация: 11 |
Можно выбрать только одну строку и одинстолбец?
|
DarkWishmaster |
4.07.2011 22:11
Сообщение
#3
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
|
Krjuger |
5.07.2011 0:24
Сообщение
#4
|
Профи Группа: Пользователи Сообщений: 652 Пол: Мужской Реальное имя: Алексей Репутация: 20 |
Самый простой вариант сделать полный перебор)))Но производительность будет аховая....
Насамом деле я думаю,если внести в твою идею некоторые корректировки,то что то путное выйдет.Смотри у тебя есть 2 варианта,либо ты умножаеш строку либо столбец.Как варант,ты находиш максимальную сууму в строке,Если надо изменить всю строку,то ты меняеш и ничего не делаеш со столбцами,если чтобы достигнуть максимума тебе в строке надо изменить 1 или 2 элемента(я отталкиваюсь от твоей матрици),то ты совершаеш эти действия для подматрицы без первой строки и дальше смотриш,если разница сумм исходной и измененной подматриц больше нуля,то ты применяеш изменения для исходной матрици,если меньше нуля,то сравниваеш это число и тем,на сколько больше нам удалось получить от изменени в первой строке,если все таки первая строка нам позволит увеличить сумму то применяеш,если нет,то отменяеш изменения и переходиш на 2 строку и все аналогично. Больше пока что ничего в голову не лезет.Задача явно переборная и надо максимально сократить этот перебор.У моего варианта достаточно много минусов,постараюсь придумать вариант получше. |
Lapp |
5.07.2011 1:52
Сообщение
#5
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Самый простой вариант сделать полный перебор)))Но производительность будет аховая.... <...> Задача явно переборная и надо максимально сократить этот перебор.У моего варианта достаточно много минусов,постараюсь придумать вариант получше. Krjuger, перебор по какому параметру? )-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Unconnected |
5.07.2011 1:56
Сообщение
#6
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Перебирать тут наверное оочень долго можно.. может, запомнить самые потенциально интересные строки\столбцы (где по модулю отриц. больше), и в каждом переборе от них плясать (заканчивать тогда, когда полезную инверсию сделать уже нельзя)?
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Lapp |
5.07.2011 8:49
Сообщение
#7
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
DarkWishmaster, ограничения на размеры матрицы накладываются?
-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
IUnknown |
5.07.2011 9:03
Сообщение
#8
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата перебор по какому параметру? ) По всем вариантам от 0 до (2N - 1) и от 0 до (2M - 1), разумеется. Если бы ТС указал, какие значения могут принимать M, N - может быть этот вариант и не родился бы. А так - для не очень больших значений он вполне работоспособен:Если M, N могут быть большими, сюда можно даже не смотреть (Показать/Скрыть)
|
DarkWishmaster |
5.07.2011 11:39
Сообщение
#9
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
DarkWishmaster, ограничения на размеры матрицы накладываются? Да, извините, совсем забыл: 1<=N,M<=18, Добавлено через 15 мин. Да, извините, совсем забыл: 1<=N,M<=18, IUnknown, Обьясните пожалуйста вот эту строку:
Ещё это $1. Я так понял если (rows shr i) четно то выдает 0 иначе 1. |
IUnknown |
5.07.2011 12:16
Сообщение
#10
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата овсем забыл: 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)... Вот такая небольшая хитрость Сообщение отредактировано: IUnknown - 5.07.2011 12:18 |
DarkWishmaster |
5.07.2011 12:40
Сообщение
#11
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
IUnknown,
Надеюсь я понял: первые два цикла перебирают абсолютно все комбинации столбцов и линий в двоичной системе, а последнее два считывают суму этого варианта. Супер! Самое интересное что матрицу это никак не изменяют. Сообщение отредактировано: DarkWishmaster - 5.07.2011 12:41 |
TarasBer |
5.07.2011 12:57
Сообщение
#12
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Я тут подумал немного.
1. Если разешить переворачивать только столбцы, то задача становится тривиальной - надо просто перевернуть все столбцы с отрицательной суммой. 2. Мы можем для каждой комбинации переворотов строк применить задачу из п.1. Таким образом, время сокращается с O(2^(n+m)) до O((2^n) *m*n). Что ещё можно сделать, я пока не знаю. -------------------- |
DarkWishmaster |
5.07.2011 13:31
Сообщение
#13
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
IUknown,
Вообщем твое решение дает 20 баллов из 100 ( там тесты онлайн я их не видел ), нашел одно решение (100/100), вроде он тут только по столбикам идет. Эту строку пока не пойму: if i and (1 shl (j-1))>0
Сообщение отредактировано: DarkWishmaster - 5.07.2011 13:40 |
TarasBer |
5.07.2011 13:45
Сообщение
#14
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Опа, стобальное решение как моё.
> Эту строку пока не пойму: > if i and (1 shl (j-1))>0 Означает "если j-1-ый бит в числе i ненулевой". Вот ты два раза подряд просишь объяснить одинаковую строку. Сначала прочитай http://ru.wikipedia.org/wiki/Битовые_операции -------------------- |
IUnknown |
5.07.2011 13:49
Сообщение
#15
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата нашел одно решение (100/100), вроде он тут только по столбикам идет. Вот и спрашивай у автора этого решения. Я в чужом копаться не собираюсь. Мне интереснее свое написать...Кстати, если тебе надо онлайн-тесты проходить - это надо заранее указывать, я вообще бы к таким задачам не прикасался. Мало того, что решает один, а сдает - другой, так еще и не пойми какие ограничения, и по размеру, и по времени... Короче, зря написал код... Больше не повторится... |
TarasBer |
5.07.2011 13:54
Сообщение
#16
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Если бы в онлайн-тестах хотя бы примерно указывалось, почему программа не прошла тест (типа "в тесте был случай нулевого кол-ва элементов"), то это было бы нормально.
А пока что я понимаю Вольво: онлайн-тесты больше похожи на - У меня не работает твоя программа, почини! - А что вы с ней делали? - Не работает программа, я же сказал! - А какие данные примерно вы в неё забивали? - Тебе что, ещё раз повторить - твоя программа не работает? Чини то, не знаю что - это как-то глупо и неэффективно. -------------------- |
Unconnected |
5.07.2011 14:02
Сообщение
#17
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Цитата Чини то, не знаю что - это как-то глупо и неэффективно. С другой стороны, учит находить острые углы в коде, на которых может не всё работать.. хотя тяжко конечно, когда на 1 из 50 тестов ошибка, и сидишь втыкаешь, что может быть) -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
TarasBer |
5.07.2011 14:05
Сообщение
#18
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> С другой стороны, учит находить острые углы в коде
Пальцем в небо тыкать это учит. Когда тебе прямо говорят, что глюк в таком-то месте на таких-то данных и ты сразу правишь, то это учит писать правильный код намного быстрее. Потому что не тратятся мозговые ресурсы на бесполезную в реальной жизни телепатическую работу. -------------------- |
Текстовая версия | 24.05.2024 20:41 |