Задача 14.
Задаются число n>1 - размерность пространства и pазмеpы М n-мерных параллелепипедов (ai1 , ..., ain), i=1,...,M.
Паpаллелепипед может располагаться в пространстве любым из способов, при которых его ребра параллельны осям координат. Найти максимальную последовательность вкладываемых друг в друге паpаллелепипедов.
|
Решение задачи 14.
Зафиксируем какой-нибудь порядок перечисления ребер параллелепипеда.
Очевидно, что параллелепипеды можно повернуть так, чтобы размеры ребер параллелепипеда шли в неубывающем порядке. Опять же понятно, что параллелепипед с большим объемом нельзя вложить в параллелепипед с меньшим объемом, вложение параллелепипеда B в C возможно только тогда, когда для двух параллелепипедов B(b(1), ..., b(n)) и C(c(1), ..., c(n)) выполняются неравенства b(k)<=c(k), k=1, ..., n. Запишем это так:
(b(1), ..., b(n))<=(c(1), ..., c(n)).
Алгоритм:
1. Сортируем размеры граней каждого параллелепипеда в неубывающем порядке.
2. Сортируем последовательность параллелепипедов по неубыванию объема.
3. Применяем алгоритм задачи 20 (Глава "Рекуррентные соотношения и динамическое программирование") для поиска максимальной по длине возрастающей подпоследовательности.
|
