Рубрики

Вариации ЛИС | DP-21

Мы обсудили решение динамического программирования для задачи с наибольшей возрастающей подпоследовательностью в этом посте и решение O (nLogn) в этом посте. Ниже приведены часто задаваемые варианты стандартной проблемы LIS .

1. Построение мостов: рассмотрим двухмерную карту с горизонтальной рекой, проходящей через ее центр. На южном берегу есть n городов с x-координатами a (1)… a (n) и n городов на северном берегу с x-координатами b (1)… b (n). Вы хотите соединить как можно больше пар городов с севера на юг, чтобы мосты не пересекались. При соединении городов вы можете соединить только город i на северном берегу с городом i на южном берегу.

8     1     4     3     5     2     6     7  

--------------------------------------------
  
--------------------------------------------
1     2     3     4     5     6     7     8

Источник: Проблемы практики динамического программирования . Ссылка также хорошо объяснила решение проблемы.
Решение этой проблемы было опубликовано здесь .

2. Последовательность увеличения максимальной суммы: задан массив из n натуральных чисел. Напишите программу для поиска подпоследовательности максимальной суммы данного массива так, чтобы целые числа в подпоследовательности сортировались в порядке возрастания. Например, если input равен {1, 101, 2, 3, 100, 4, 5}, то выходной сигнал должен быть {1, 2, 3, 100}. Решение этой проблемы было опубликовано здесь .

3. Самая длинная цепь Вам даны пары чисел. В паре первое число меньше второго числа. Предположим, у вас есть два набора (a, b) и (c, d), второй набор может следовать за первым набором, если b <c. Таким образом, вы можете сформировать длинную цепочку подобным образом. Найдите самую длинную цепь, которая может быть сформирована. Решение этой проблемы было опубликовано здесь .

4. Укладка ящиков. Вам предоставляется набор из n типов прямоугольных трехмерных ящиков, где i-й ящик имеет высоту h (i), ширину w (i) и глубину d (i) (все действительные числа). Вы хотите создать стопку коробок, которая будет как можно более высокой, но вы можете сложить коробку только над другой коробкой, если размеры двухмерной основы нижнего прямоугольника строго больше размеров двухмерной. Буду основанием верхней коробки. Конечно, вы можете вращать коробку так, чтобы любая сторона функционировала как ее основа. Также допустимо использовать несколько экземпляров одного и того же типа ящика.
Источник: Проблемы практики динамического программирования . Ссылка также хорошо объяснила решение проблемы.

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

Рекомендуемые посты:

Вариации ЛИС | DP-21

0.00 (0%) 0 votes