Форум программистов, компьютерный форум CyberForum.ru

Метод потенциалов на максимизацию - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
11.10.2012, 22:41     Метод потенциалов на максимизацию #1
Всем доброго времени суток. Столкнулся с проблемой нехватки алгоритма.
Входные данные два массива одинаковой размерности. В первом множители. Во втором умножаемые. Оба массива уже заполнены.
Нужно получить максимальную сумму произведений элементов массива на массив. A[i][j]*B[i][j] и так каждый с каждым и все сложить. Условие в том что должна сохраняться сумма по каждой строке и каждому столбцу. Очень похоже на метод потенциалов. Даже это может и метод потенциалов но я не найду на него инфу что бы делать на максимум. Скорее всего надо какой то коэффициент поменять или условия... Подскажите алгоритм ) Пожалуйста )

P.S. Алгоритм это не готовая задача. Не нужно писать готовые куски кода )
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
11.10.2012, 22:46     Метод потенциалов на максимизацию #2
т.е. нужно при перемножении каждого с каждым найти максимальное произведение?

или как сумму? суммму чего и чего?
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
11.10.2012, 23:42  [ТС]     Метод потенциалов на максимизацию #3
Цитата Сообщение от MrGrig Посмотреть сообщение
т.е. нужно при перемножении каждого с каждым найти максимальное произведение?

или как сумму? суммму чего и чего?
Элементы первого массива статичны. Нужно переставлять элементы второго массива так что бы получить максимальную сумму произведений: а11*в11+а12*в12+...+а57*в57+... И причём при этих перестановках нужно сохранять сумму по строкам и столбцам.
Если у нас массив:
10 40
0 30

то можно переставить так:
0 50
10 20

Мы сделали перестановку и поменяли их местами.

Добавлено через 37 минут
Мне кажется или я очень сильно тупанул или ... не знаю что или. все мои предположения про метод я сказал (
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.10.2012, 00:00     Метод потенциалов на максимизацию #4
GagarinSokol, А по-моему Вам нужно сделать так:
максимально элементу массива A[][] подставить максимальный элемент в тоже место массива b[][]. Второму по значимости элементу массива A[][] подставить второй по значимости элемент в тоже место массива b[][]. И т.д.
Т.е. Если имеем:

Цитата Сообщение от GagarinSokol Посмотреть сообщение
Если у нас массив:
10 40
0 30
то можно переставить так:
0 50
10 20
То нужно, чтобы второй массив стал таким:
10 50
0 20
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
12.10.2012, 00:09     Метод потенциалов на максимизацию #5
нет товарищ имеет ввиду что во втором масиве сумма по столбцам и строкам остается неизменной, очень похоже на задачу по оптимальности. почитайте решение транспортной задачи, возможно это как то вам поможет...
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
12.10.2012, 19:28  [ТС]     Метод потенциалов на максимизацию #6
Цитата Сообщение от MrGrig Посмотреть сообщение
нет товарищ имеет ввиду что во втором масиве сумма по столбцам и строкам остается неизменной, очень похоже на задачу по оптимальности. почитайте решение транспортной задачи, возможно это как то вам поможет...
Да всё верно это чисто транспортная задача, НО её надо решать на максимум...

Может кто знает?

Добавлено через 19 часов 2 минуты
Что подскажите по проблеме?
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
12.10.2012, 21:31  [ТС]     Метод потенциалов на максимизацию #7
Может кто что ещё подкинет?

Сформулирую по другому:
есть 7 видов ресурсов и 8 потребителей. Каждый вид ресурса для каждого потребителя имеет определённую полезность она казана в статичной таблице. У каждого поставщика имеется определённое количество ресурсов, а каждому потребителю требуется определённое количество ресурса. Нужно распределить ресурсы так что бы все потребители получили все ресурсы и причём с максимальной пользой.

Вот текст задачи. Может кто то решал уже? Сейчас делаю методом потенциалов как на минимум только немного по другому. не знаю что из этого получится.
Вложения
Тип файла: doc Задание.doc (32.0 Кб, 10 просмотров)
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
12.10.2012, 21:48  [ТС]     Метод потенциалов на максимизацию #8
и немного не понятно если мы делаем на минимум то нам не нравятся клетки где C~ > C , а условие остановки все C > C~ .

А если на максимум делать? Тоже самое условие получается или нет...

Посмотрел думаю что на оборот. C~ < C их используем. А условие остановки вычислений C~ > C
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
12.10.2012, 22:00     Метод потенциалов на максимизацию #9
ну можно посмотреть вообще как меняется т.к. заполненость нулями 2й матрицы от произведения опытным путем на каком нибудь примере 2х2 или 3х3 или погуглить. узнав ответ, соответственно строить алгоритм, где, либо будет много нулей и несколько больших значений, либо где будет мало нулей и все значения будут примерно равны

Добавлено через 1 минуту
Цитата Сообщение от GagarinSokol Посмотреть сообщение
Задание.doc (32.0 Кб, 0 просмотров)
это кстати уже задача о рюкзаке....

Добавлено через 34 секунды
http://ru.wikipedia.org/wiki/%D0%97%...BD%D1%86%D0%B5

я и забыл что они взаимно обратные, вот только как вы переформулировали задачу я вспомнил =)
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
13.10.2012, 00:06  [ТС]     Метод потенциалов на максимизацию #10
Цитата Сообщение от MrGrig Посмотреть сообщение
ну можно посмотреть вообще как меняется т.к. заполненость нулями 2й матрицы от произведения опытным путем на каком нибудь примере 2х2 или 3х3 или погуглить. узнав ответ, соответственно строить алгоритм, где, либо будет много нулей и несколько больших значений, либо где будет мало нулей и все значения будут примерно равны

Добавлено через 1 минуту


это кстати уже задача о рюкзаке....

Добавлено через 34 секунды
http://ru.wikipedia.org/wiki/%D0%97%...BD%D1%86%D0%B5

я и забыл что они взаимно обратные, вот только как вы переформулировали задачу я вспомнил =)
посмотрел задачу о рюкзаке. немножко не понимаю как применить.

Но кстати сейчас вот то что выше я написал работает ) Только теперь проблема с постройкой циклов. У меня строятся простые циклы. а вот как построить сложные циклы это надо подумать....

Добавлено через 28 минут
И ещё интересный момент а не будет ли сложный цикл = нескольким простым ??????
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.10.2012, 00:44     Метод потенциалов на максимизацию
Еще ссылки по теме:

Транспортная задача (методом потенциалов) C++
C++ Как передать в метод класса Menu указатель на метод дочернего класса?
Транспортная задача (методом потенциалов) C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
14.10.2012, 00:44  [ТС]     Метод потенциалов на максимизацию #11
Задача решена.

Для транспортной на максимум :

Использовал для старта клетку где максимальная : C - C~ что означает что нам не нравятся клетки где C > C~

Условия остановки все С <= С~

С = полезность определённого ресурса для определённого потребителя.
С~ = это сумма альфа и бета в данной клетке.

Про циклы: несколько маленьких циклов не заменяют один большой.

Использовал построение больших циклов. Для построения больших циклов использовал волновой алгоритм.

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

Если кому то нужны вопросы по реализации данной задачи спрашивайте тут или пишите на почту: мой_ник_на_форуме@gmail.com

Всем спасибо )
Yandex
Объявления
14.10.2012, 00:44     Метод потенциалов на максимизацию
Ответ Создать тему
Опции темы

Текущее время: 11:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru