| Сергей | Дата: Вторник, 12.01.2010, 15:41 | Сообщение # 16 |
 Лейтенант
Группа: Модераторы
Сообщений: 43
Статус: Offline
| Задача 8. «Перестановки»
Полное решение данной задачи основано на использовании динамического программирования и эффективном кодировании подмножества исходного множества. В качестве подзадач здесь следует рассматривать задачи, аналогичные исходной, но для некоторого подмножества исходного множества чисел.
Выберем в качестве состояния пару из подмножества P исходного множества S и номера выделенного элемента j в нем. Для каждого состояния будем хранить количество существующих k–перестановок из элементов данного подмножества P, но только таких перестановок, в которых последний элемент имеет номер j (в исходной нумерации). Начальное состояние в этом случае будет P=Ø. При программной реализации подмножество P удобно хранить с помощью битовых масок.
Рекуррентные формулы для переходов можно представить на основе того, что к множеству можно добавить элемент, который в нем не содержится. Реализация перехода не представляет особых трудностей. Единственное, о чем необходимо помнить, – после заполнения таблицы динамического программирования требуется выполнить восстановление ответа, последовательно определяя, какое число поставить на очередную позицию.
Описанные алгоритм имеет время работы O(m22m). Несмотря на то, что данное решение работает за экспоненциальное время, оно значительно быстрее простого перебора.
|
| |
| |
