Динамическое программирование. Метод построения алгоритмов решения оптимизационных задач, страница 2

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Сделано предположение, что этот алгоритм остановится для любого целого числа n. Оно проверено для всех чисел в интервале от 0 до 1000000.

Для заданного n количество чисел, которые печатает алгоритм, назовем len(k). Для приведенного примера len(22)=16.

Для заданных целых i и j необходимо найти наибольшее значение len(k) среди всех целых k, таких что i ≤ k ≤ j.

Составьте эффективный алгоритм, решающий поставленную задачу.

3.  Наибольшая общая подпоследовательность

Заданы две последовательности. Необходимо найти общую подпоследовательность наибольшей длины.

Подпоследовательность получается из данной последовательности, если удалить некоторые ее элементы.

Подпоследовательность является общей двух последовательностей, если она является подпоследовательностью как одной, так и другой последовательности.

Указание. Заметьте, что если обе последовательности заканчиваются (или начинаются) одинаковыми элементами, то искомая подпоследовательность также заканчивается (или начинается) этим элементом.

4.  Битоническая евклидова задача коммивояжёра

Евклидова задача коммивояжёра состоит в нахождении кратчайшего замкнутого пути, соединяющего данные n точек на плоскости. Эту задачу вряд ли можно решить за полиномиальное время.

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

Постройте алгоритм решения этой задачи, требующий времени O(n²).

Указание. Считайте, что абсциссы всех точек разные. Просматривая точки слева направо, храните для текущей точки x и для всех предыдущих точек y длину кратчайшего пути, битонически соединяющего x с y с проходом через крайнюю левую точку.

5.  Оптимальная резка

Есть бревно длины l. Его необходимо распилить в заданных местах x₁…x_n. Стоимость одного распила линейно зависит от длины бревна. За один раз можно распилить бревно только в одном месте. Составьте эффективный алгоритм решения задачи. (Числа l, x₁…x_n – целые.)

Например, длина бревна составляет 10, его необходимо распилить в точках 2, 4 и 7, считая с одного конца. Если сначала пилить в точке 2, потом в 4, потом в 7, то цена распиливания будет 10+8+6=24. Если же сначала пилить в точке 4, потом в 2, потом в 7, то цена распиливания будет 10+4+6=20.

6.  Очередь

Обменный пункт открывается утром и в нем нет долларов. В обменный пункт стоит очередь из m+n человек. При этом n человек имеют $100 одной купюрой и хотят разменять ее и получить $50 сдачи. Другие m человек имеют $50 одной купюрой и хотят обменять ее целиком. Необходимо вычислить количество таких расстановок человек в очереди, при которых не возникает задержек из-за отсутствия в пункте долларов.

7.  Задача о ранце

Вор пробрался на склад, на котором хранится n вещей. Вещь номер i весит w_i и стоит v_i (w_i и v_i - целые числа). Вор хочет украсть товара на максимальную сумму, причем максимальный вес, который он может унести в рюкзаке, равен W (число W – тоже целое). Что он должен положить рюкзак?

Постройте алгоритм решения этой задачи, требующий времени O(nW).

8.  Разбиение абзаца строки

Абзац текста состоит из n слов длиной l₁, l₂… l_n. Считая, что все символы имеют равную ширину, мы хотим оптимальным образом разбить его на строки длиной не более M символов. Оптимальность при этом определяется так: посчитаем число «лишних» пробелов в каждой строке (то есть посмотрим, на сколько длина строки меньше М, если между словами ставить по одному пробелу) и сложим кубы этих чисел для всех строк, кроме последней: чем больше эта сумма, тем хуже абзац.

Разработайте алгоритм оптимального разбиения абзаца на строки.

4  Список литературы

Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Построение и анализ, М., МЦНМО.

В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования. Издательство Фолио. Харьков, 1997.