green_2005По-моему, это задача раскроя.
Решается методами линейного программирования.Можно, конечно, и линейным, но как-то из пушки по воробьям.
Я бы решал "теорией голодной козы", построив геометрическое место точек, где может находиться центр нового прямоугольника. То есть я бы внешний прямоугольник уменьшил на w1 по ширине и h1 по высоте (получил бы (x1+0.5*w1, y1+0.5*h1, x2-0.5*w1, y2-0.5*h1), в него накидал аналогично увеличенных мелких прямоугольников, где внешний прямоугольник оказался не закрыт, там можно разместить центр нового прямоугольника. Если новый можно крутить, то повторить процедуру, поменяв w1 и h1 местами.

_some_Предлагаю продолжить методом Монте-Карло:
Так же произвольно, как и первые пять, кидаем шестой прямоугольник. Если он лег удачно (без перекрытий) - так и оставляем. Если нет, повторяем еще раз до победного конца, но не более заранее оговоренного числа раз.Предлагаю так суда грузить. Кидаем трактор в трюм. Если он лег удачно (без перекрытий) - так и оставляем. Если нет, повторяем еще раз до победного конца, но не более заранее оговоренного числа раз.

_some_iv_an_ru Предлагаю так суда грузить. Кидаем трактор в трюм. Если он лег удачно (без перекрытий) - так и оставляем. Если нет, повторяем еще раз до победного конца, но не более заранее оговоренного числа раз.А оно разве грузится как-то по-другому?Академик Крылов в своих мемуарах подробно описывает загрузку некоторых сухогрузов как своё отдельное серьёзное достижение. А вообще почти всегода стивидором рулит дяденька с профильным в/о и хорошим стажем.[/quot]

_some_,

Раскрой одно время был вообще модной темой, (а распил ещё моднее)

Яростный МечНавскидку можно так (насчет оптимальности большие сомнения):
У меня тоже. Можно быстрее.
1. Мысленно растягиваем отрезки-стороны маленьких прямоугольников так, чтобы они упёрлись в края экрана. То есть каждый прямоугольник превращается в эдакую '#'.
2. Теперь весь большой прямоугольник разграфлён на клеточки разного размера. Если координаты нигде не повторяются, то клеточек будет 13*13=169, если повторяются то меньше. Вполне мелкая матрица.
3. Делаем целочисленную матрицу такого размера, заливаем нулями, потом "рисуем" в ней уже имеющиеся прямоугольники, забивая целое число клеточек номером прямоугольника.
4. Теперь не проблема пробежаться по матрице, разыскивая прямоугольник нулей подходящих габаритов.

Этот алгоритм юзался до Win2000 включительно в оконной системе, потом наши Нские люди предложили более быстрый, который я тут повешусь расписывать.

_some_Главный вывод из той статьи: Задача раскроя не имеет внятного аналитического решения. Поэтому и возились с эвристиками.Ясен пень, раз одномерные задачи о ранцах и то сплошь NP-противные, двумерный аналог тем более будет NP.