Flip, найти максимальную сумму матрицы путем умножения линий и столбиков на |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Flip, найти максимальную сумму матрицы путем умножения линий и столбиков на |
DarkWishmaster |
Сообщение
#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, но такой способ не помогает так как когда мы умножаем линию то изменются и колоны и наоборот. |
IUnknown |
Сообщение
#2
|
Гуру Группа: Пользователи Сообщений: 1 013 Пол: Мужской Ада: Разработчик Embarcadero Delphi: Сторонник Free Pascal: Разработчик Репутация: 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 - |
DarkWishmaster |
Сообщение
#3
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
IUnknown,
Надеюсь я понял: первые два цикла перебирают абсолютно все комбинации столбцов и линий в двоичной системе, а последнее два считывают суму этого варианта. Супер! Самое интересное что матрицу это никак не изменяют. Сообщение отредактировано: DarkWishmaster - |
Текстовая версия | 5.05.2024 5:23 |