@leysanka

есть три множества одинаковой мощности-мужчины женщины и дома. (все по n)
между мужчинами и женщинами есть симпатии.
и мужчинам:cofee2: и женщинам нравятся некоторые дома.
сколько обоюдносимпатизирующих пар можно заселить в нравящийся им дом?
т.е. надо вывести кол-во идеальных вариантов..
социально важная задача, кстати!

0

@RUSya82

это С++?

0

@Patch

это SQL.
но можно извратиться, и реализовать циклы на C/C++

0

@leysanka

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

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

0

valeriikozlov

Изначально задача кажется немного странной.
Это все условие:?
Тогда вопросы:
- мощности-мужчины женщины и дома как нибудь связаны с симпатиями:
между мужчинами и женщинами и понравившимися домами?
- как задаются входные данные вообще?
Насчет социально важной задачи Вас обманули кстати, все решается не так (а через знакомства, взятки и т.п.)

0

@Patch

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

по сути - типичная шахматная задача.

0

valeriikozlov

Это называется "жадный алгоритм", но пока неизвестно по какому принципу формируются входные данные этот алгоритм применять преждевременно.

0

@Patch

по-моему, как раз это понятно.
принцип формирования исходных данных четко описан:
другое дело, что эти данные можно представить в разных форматах.
но формат исходных данных на алгоритм практически не влияет.

а еще есть вопрос, как могут заселяться дома: обязательно по одной паре на дом, или можно по нескльку?

0

valeriikozlov

А по-моему не совсем все-таки понятно. Например если мощности и симпатии согласуются по принципу: если мощность мужчины, женщины или дома расходятся не более чем на 5 единиц, то все друг другу нравятся. А если более, то не нравятся. То тогда жадный алгоритм не применим, для достижения максимального результата.
Лучше все-таки дождаться ответа хозяйки вопроса.

0

@Patch

смысл фразы ускользает.
что в данном контексте "мощность мужчины"?
Мощность множества
ваша терминология отличается от общепринятой?

0

@leysanka

эм. ну. вообще это произвольная задача-задание графов делать как удобнее и как быстрее.
да,задача на перебор.
одна пара один дом.
делать можно практически все что захочется главное-решить задачу и использованием графов, ибо задача по теории графов.

я сейчас голову себе отвинчу.
мне понравился простейший вариант.как его реализовывать? простите что не сразу отвечаю-сижу получаю зачет по физике

0

valeriikozlov

Да нет, не отличается. Наоборот совпадает.
Хорошо вот еще простой пример:
Мужчине №1 нравится женщина №1 и им обоим нравятся дома номер №1 и №2.
Мужчине №2 нравится женщина №2 и им обоим нравится дом номер №1.
Если следовать жадному алгоритму (который Вы привели), то можно заселить одну пару в один дом.
А на самом деле можно заселить 2 пары.
Поэтому все-таки предлагаю:

0

@Patch

нет.
если следовать моему алгоритму, то в перебор попадут ОБА варианта.

0

valeriikozlov

А как же:

0

@leysanka

эм.меня кто-нибудь слыыышит?
одна пара-один дом- и выкинуть из процесса.
ибо коммуналки разводить негоже.капитализм все-таки.

0

@Patch

сильно зависит от того, на какие ресурсы расчитывать(в плане вычислительной мощность и объема памяти компьютера).
если особых ограничений нет, то, опять-же, простейший вариант:

а)создать структуры:
1)женщина:
массив из n двоичных элементов(отражающий ее симпатии), по одному на каждого мужчину
значение 1 - есть симпатия, 0 - нет симпатии
еще одна переменная целого типа - номер пары, в которой состоит женщина. соответственно, 0 - не состоит.
2)мужчина
- то-же самое, что и у женщины
3)дом
одна переменная - номер заселенной пары. 0 - пары нет.

б)создать массивы мужчин, женщин и домов.
запихнуть все это в одну структуру.
добавляем туда-же счетчик заселенных домов

сделать и заполнить "рабочий" экземпляр этой главной структуры(из файла, или случайными данными - это вы сами решайте).
сделать "оптимальный" экземпляр главной структуры - туда будут сохраняться наилучшие найденные варианты.

далее...

перебираем женщин, их симпатии( выраженные массивом двоичных элементов), для каждой проверяем незанятых мужчин, и свободные дома.
если находим пару с домом :
1) увеличиваем счетчик найденных домов, сравниваем с "оптимальным" вариантом.
если новый вариант лучше - копируем его в оптимальный.
2)сохраняем текущее состояние("рабочую структуру") в стек.

когда все женщины/мужчины/дома заканчиваются - восстанавливаем из стека предыдущий вариант, и считаем дальше так, будто его не было.

таким образом, будут рассмотрены ВСЕ возможные комбинации женщин/мужчин/домов

собственно, все.

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

но стек, при большом n может понадобиться очень приличного размера.

1

valeriikozlov

Patch, что-то я в Вашем алгоритме не увидел:
Насчет:
наверное все-таки "оптимальный" (по крайней мере, по выделяемой памяти) это когда двумерный массив размером n*3 (можно и через структуры) и в котором каждая строка примерно такая:
5 6 3 - что означает 5-ый мужчина обоюдносимпатизирует 6-ой женщине и им обоим нравится 3-ий дом.

0

@Patch

это исходное условие. его нужно отдельно описывать?

нет, "оптимальный" в данном случае - наилучший с точки зрения поставленной задачи.
а если говорить об оптимальности с точки зрения памяти/исполнения, то лучше списками делать не только симпатии, но и вообще всю структуру. и работать будет существенно быстрее.
кроме того, можно сделать алгоритм взвешивания группы решений, кэширование найденных пар-домов и т.д. и т.п. теории баз данных и параллельных вычислений позволяют много чего сделать.
я-же писал "простейший вариант".
или, скажем так, наиболее понятный человеку неподготовленному.

0

valeriikozlov

а я почему-то считаю что с помощью графов (матрицы смежности) намного быстрее и легче узнать обоюдносимпатизирующих женщин и мужчин например.

0

@easybudda

0