0 / 0 / 0
Регистрация: 27.04.2014
Сообщений: 8
|
|
1 | |
Организовать перебор всех возможных сочетаний21.05.2014, 22:38. Показов 3865. Ответов 15
Метки нет (Все метки)
Затрудняюсь с алгоритмом. Как можно организовать перебор всех возможных группировок?
Имеется несколько романов одного писателя. Для каждого из них известен объем (число страниц). Для издания сочиннения романы надо сгруппировать в пары. Каждая пара будет печататься в одном томе. Если число романов нечетно, то один печатается в отдельном томе. Требуется найти такую группировку, при которой объем самого толстого тома минимален.
0
|
21.05.2014, 22:38 | |
Ответы с готовыми решениями:
15
Перебор и вывод всех возможных сочетаний Перебор всех возможных сочетаний заданных переменных Комбинаторика, перебор всех сочетаний Перебор всех возможных вариантов (рекурсивно) |
543 / 486 / 104
Регистрация: 05.05.2014
Сообщений: 1,110
|
|
21.05.2014, 23:44 | 2 |
Shout, Пока в голову пришла только только такая тривиальная мысль, что для нечетного количества романов надо создать фиктивный роман объемом 0 страниц, и дальше работать только с четными.
Но задача интересная. Надо подумать на свежую голову... Добавлено через 42 минуты Это называется "Разбиение на блоки". Алгоритм есть в книжке Липски, которой к сожалению сейчас нет под рукой. Но думаю, и в других книжках по комбинаторным алгоритмам он должен быть. К сожалению, их под рукой тоже нет, Только топор да лопата
2
|
Комп_Оратор)
|
|
22.05.2014, 00:09 | 3 |
Я не уверен, но как фантазия:
Минимальный объём это сумма максимального и минимального элементов. Выбрав пару и сложив (для контроля ) сохраняем пару. То же делаем из оставшихся пока не кончатся. Может разделить сортированный ряд пополам и перевернув одну из половинок почленно сложить со второй? Это гарантирует сложение максимального и минимального элементов. То есть то же самое, но быстрее.
0
|
543 / 486 / 104
Регистрация: 05.05.2014
Сообщений: 1,110
|
|
22.05.2014, 10:23 | 4 |
Shout, После нахождения алгоритма разбиения на блоки для сокращения объема вычислений вам , скорее всего, надо будет применить "метод ветвей и границ"
Добавлено через 1 минуту Это я к тому, чтобы вы знали в какую сторону копать дальше...
0
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
23.05.2014, 18:54 | 6 | |||||
2
|
Комп_Оратор)
|
|||||||||||
24.05.2014, 00:32 | 7 | ||||||||||
Mr.X, классный код и я сразу прошу прощения за тот вариант который выкладываю. У меня нет С++11 и я попытался адаптировать к своему компилятору, вдруг у кого-то та же история . Если где-то ошибся, - не обессудьте.
1
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
24.05.2014, 06:09 | 8 |
2
|
Комп_Оратор)
|
|
24.05.2014, 11:53 | 9 |
Понятно. То есть задача про романы, это просто иллюстрация, а главная цель, - перебор и сравнение всех возможных вариантов, сама по себе? Тогда моё выступление не в тему.
Однако в формулировке задачи остаётся слово "сравнение". Наверное в зависимости от способа сравнения/сопоставления существуют если не обязательно доказательства, но хотя бы способы сокращения объёма? Ведь перебор всех вариантов, как следует из комбинаторики, это штука затратная? Тем не менее спасибо за ответ. Хороший алгоритм перебора всех вариантов сочетаний, это самостоятельная и серьёзная задача.
0
|
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
24.05.2014, 12:00 | 10 |
Кнут, "Искусство программирования", том 4, выпуск 3 - "Генерация всех сочетаний и разбиений".
Сам не разбирался с вопросом, поэтому конкретнее сказать ничего не могу.
1
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
24.05.2014, 15:26 | 11 | |||||
Кстати, насчет эффективности. Я, особо не размышляя, поставил обход начиная с толстых двухтомников. А сделал начиная с тонких, и скорость работы увеличилась на порядок:
1
|
Комп_Оратор)
|
|
24.05.2014, 17:15 | 12 |
Я вот, как раз, об этом. Какие стратегии использовать в том или ином случае? С мат. доказательством для этой задачи не должно быть трудностей. Например:
Поскольку переход от нечётного количества к чётному тривиален, то докажем для чётного. В каждом множестве есть один или несколько элементов категории максимальный и минимальный. Разумеется первая выборка должна включать пару элементов каждой из этих категорий, поскольку любая другая комбинация даст больший результат. Попытка выбрать для не максимального минимальный элемент и сформировать данную пару из соображений "пусть эта будет ещё меньше", приведёт к тому, что максимальный обречён на пару с элементом более минимального (если тот на данной выборке один) и тогда максимальный 2-х томник увеличится в сравнении с полученным по правилу "каждый раз выбирай максимально противоположные". Я не математик и мои суждения могут быть наивны, но кажутся логичными. Впрочем, я уже понял, что суть данной задачи не ограничена её предметом, а подобное доказательство всегда тесно с ним связано. Это ограничивает общность самого подхода. Пока, тем не менее видно, что границы сравнений/сопоставлений в условии выборки и в условиях конечного результата связанны и анализ этой связи может существенно сократить объём.
0
|
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
25.05.2014, 08:26 | 13 |
Наверное, у меня тут нет права критиковать, поскольку в теме сам не очень понимаю, но все-таки...
Почитайте Кнута. У него в принципе другой подход к задаче. Не эвристические сортировки и переборы, а вполне конкретный алгоритм генерации разибения. У него описано несколько алгоритмов. Среди них есть для генерации всех возможных разбиений множества. Он достаточно понятно описан и просто реализуется. А еще есть алгоритм генерации разбиения множества на m блоков - и вот тут какой-то ад. Присутствует только словесное описание (с 168) алгоритма с двумя рекурсивными функциями, которые вызывают еще и друг друга. Вот с ними я не разобрался - либо перевод невнятный, либо у меня мозгов не хватило. Мб кто-нибудь осилит. И без обид, но от приведенного в теме решения лично у меня глаза вытекают. Добавлено через 15 часов 2 минуты Нашел рализацию на джаве. Сам алгоритм занимает 20 строк. https://github.com/coderodde/l... rator.java
1
|
Tulosba
|
25.05.2014, 12:10
#14
|
0
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
26.05.2014, 20:26 | 15 |
Сформулировал-таки доказательство:
Пусть R – оптимальное разбиение множества S на пары, т.е. пара его элементов (m, M) с максимальной суммой имеет минимально возможное значение этой суммы. Добавим к R еще пару (n, N) элементов таких, что в отсортированном массиве значений элементов они стоят на концах. Докажем, что новое разбиение R1, состоящее из R и пары (n, N), также является оптимальным. а) Пусть n + N >= m + M. Докажем, что не существует разбиения, в котором максимальная сумма пары была бы меньше n + N. Действительно, если такое разбиение существует, то в нем нет пары (n, N), т.е. элемент N там сочетается с неким элементом k. Но элемент n самый левый, следовательно n <= k и n + N <= k + N, т.е. максимальная сумма пары в этом разбиении не меньше n + N. б) Пусть n + N < m + M. Докажем, что не существует разбиения, в котором максимальная сумма пары была бы меньше m + M. Предположим, что такое разбиение существует. 1) Пусть в этом разбиении присутствует пара (n, N). Тогда, удалив ее, мы получим разбиение множества S с максимальной сумой пары меньше, чем m + M, что противоречит условию. 2) Пусть в этом разбиении отсутствует пара (n, N). Тогда элемент n сочетается с неким элементом B из множества S. Но элемент N самый правый, следовательно B <= N. Удалив из разбиения пару (n, B), мы получим разбиение R2 множества S, в котором элемент B заменен на не меньший элемент N, но при этом максимальная сумма пары (m1, M1) меньше, чем m + M. Заменим в разбиении R2 элемент N обратно на B. Мы получим разбиение множества S, в котором сумма каждой пары не больше m1 + M1, т.е. меньше m + M, что противоречит условию. Из вышедоказанного следует, что разбиение множества значений на пары, элементы которых равноотстоят от концов отсортированного массива значений, является оптимальным.
3
|
543 / 486 / 104
Регистрация: 05.05.2014
Сообщений: 1,110
|
|
26.05.2014, 23:03 | 16 |
Дотошно не проверял, но верю. Уж больно убедителен стиль изложения.
И вообще, во время вскапывания огорода, меня часто посещала мыслишка, что все сложное - просто.
2
|
26.05.2014, 23:03 | |
26.05.2014, 23:03 | |
Помогаю со студенческими работами здесь
16
Реализовать перебор всех возможных IP-адресов (С++) Перебор всех возможных подмножеств множества целых чисел Перебор всех возможных вариантов с переменными приравненных к определенному значению Перебор всех возможных подмножеств заданного множества целых чисел Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |