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

Вывести количество идеальных вариантов - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ fscanf(stream,"%s",s) читает до первого пробела? http://www.cyberforum.ru/cpp-beginners/thread221726.html
как прочитать строку из текстового файла целиком? (до \n)
C++ Односвязный кольцевой список. Ребят, подскажите как реализовать односвязный кольцевой список с ключами. Без ключей я знаю как, а что делают эти самые ключи? http://www.cyberforum.ru/cpp-beginners/thread221725.html
кириллица C++
Подскажите, как сделать ,чтобы в Borland C вывод был русскими буквами. Я написал setlocale(LC_ALL, "Russian"); вывод стал на кириллице,а вот информацию которую вводишь - нет
Удаление из строки всех символов, коды которых попадают в заданный диапазон C++
написать функцию удаления из строки s всех символов ASCIIкоды которых попадают в диапозон от н1 до н2 включительно 0<=н1<=255,0<=н2<=255, н1<=н2 помогите!
C++ Блок схема http://www.cyberforum.ru/cpp-beginners/thread221712.html
Люди помогите! =( Написал программу на Паскале и не могу схему алгоритма начертить, запутываюсь постоянно..Нарисуйте кто может и залейте куда нибудь, оч прошу =). Вот программа: uses crt; var ...
C++ Построение центра дерева (графы) Задача состоит в том, что нужно найти центр дерева, и при этом алгоритм должен учитывать особенность графов этого типа (центр содержит одну или две смежные вершины). Пробовал через матрицу смежности... подробнее

Показать сообщение отдельно
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
28.12.2010, 17:11
Цитата Сообщение от leysanka Посмотреть сообщение
мне понравился простейший вариант.как его реализовывать?
сильно зависит от того, на какие ресурсы расчитывать(в плане вычислительной мощность и объема памяти компьютера).
если особых ограничений нет, то, опять-же, простейший вариант:

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

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

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

далее...

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

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

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

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

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

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