Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
#1

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

11.10.2012, 22:41. Просмотров 1489. Ответов 10
Метки нет (Все метки)

Всем доброго времени суток. Столкнулся с проблемой нехватки алгоритма.
Входные данные два массива одинаковой размерности. В первом множители. Во втором умножаемые. Оба массива уже заполнены.
Нужно получить максимальную сумму произведений элементов массива на массив. A[i][j]*B[i][j] и так каждый с каждым и все сложить. Условие в том что должна сохраняться сумма по каждой строке и каждому столбцу. Очень похоже на метод потенциалов. Даже это может и метод потенциалов но я не найду на него инфу что бы делать на максимум. Скорее всего надо какой то коэффициент поменять или условия... Подскажите алгоритм ) Пожалуйста )

P.S. Алгоритм это не готовая задача. Не нужно писать готовые куски кода )
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2012, 22:41
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Метод потенциалов на максимизацию (C++):

Метод потенциалов Транспортная задача - C++
Как можно найти цикл в матрице ? нехватает этой чудо функций

СЛАУ. Метод обратной матрицы, метод Гаусса, метод Крамера, метод Зейделя - C++
Помогите ребят. Не могу построить алгоритмы для этих методов Язык C++

Метод медиан из трех элементов VS улучшенный быстрый метод сортировки(метод Бентли-Макилроя) - C++
Здравствуйте! Дали весьма интересное задание. Сравнить два вышеуказанных метода сортировки для массива из 10000 элементов, результаты...

Мой код - метод бисекции, метод секущих (метод хорд) - C++
Всем привет!!! Изучаем в институте С++. Сделал код, и там, и там одна и та же проблема - при любых вбиваемых значениях программа делает...

Транспортная задача (методом потенциалов) - C++
В универе задали сделать транспортную задачу. Знания только одного семестра ОП. Сделал заполнение таблицы поиск потенциала и проверку...

Транспортная задача (методом потенциалов) - C++
Доброго времени суток форумчане! Нужна прога по вычислению транспортной задачи методом потенциалов. Пытался сам сделать, но как-то не...

10
MrGrig
177 / 160 / 2
Регистрация: 08.10.2012
Сообщений: 422
11.10.2012, 22:46 #2
т.е. нужно при перемножении каждого с каждым найти максимальное произведение?

или как сумму? суммму чего и чего?
0
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 минут
Мне кажется или я очень сильно тупанул или ... не знаю что или. все мои предположения про метод я сказал (
0
valeriikozlov
Эксперт С++
4673 / 2499 / 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
0
MrGrig
177 / 160 / 2
Регистрация: 08.10.2012
Сообщений: 422
12.10.2012, 00:09 #5
нет товарищ имеет ввиду что во втором масиве сумма по столбцам и строкам остается неизменной, очень похоже на задачу по оптимальности. почитайте решение транспортной задачи, возможно это как то вам поможет...
0
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
12.10.2012, 19:28  [ТС] #6
Цитата Сообщение от MrGrig Посмотреть сообщение
нет товарищ имеет ввиду что во втором масиве сумма по столбцам и строкам остается неизменной, очень похоже на задачу по оптимальности. почитайте решение транспортной задачи, возможно это как то вам поможет...
Да всё верно это чисто транспортная задача, НО её надо решать на максимум...

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

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

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

Вот текст задачи. Может кто то решал уже? Сейчас делаю методом потенциалов как на минимум только немного по другому. не знаю что из этого получится.
0
Вложения
Тип файла: 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
0
MrGrig
177 / 160 / 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

я и забыл что они взаимно обратные, вот только как вы переформулировали задачу я вспомнил =)
1
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 минут
И ещё интересный момент а не будет ли сложный цикл = нескольким простым ??????
0
GagarinSokol
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 27
14.10.2012, 00:44  [ТС] #11
Задача решена.

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

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

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

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

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

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

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

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

Всем спасибо )
0
14.10.2012, 00:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.10.2012, 00:44
Привет! Вот еще темы с ответами:

Решить транспортную задачу методом потенциалов - C++
Помогите пожалуйста. Необходимо написать программу которая решает транспортную задачу методом потенциалов. Препод показал на таблицу(её...

Транспортная Задача Делфи (метод с-з угла + метод оптимизации(потенциалов) - Delphi
Ребят, столкнулся с такой проблемой: Курсовая работа &quot;Компьютерная модель решения ТЗ&quot; необходима программа, с любыми условиями, исходная...

Метод Контурных токов и метод узловых потенциалов - Электротехника
Имеется схемка,где j1=2A ;e1=2B ;e2=1B ;e3=8B; R1=2; R2=2 Om; R3=2 Om; R4= 2 Om; R5=4 Om По методу МКТ надо составить,...

Метод контурных токов, метод узловых потенциалов - Электротехника
Помогите,пожалуйста,составить системы уравнений для этих цепей


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru