Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 02.04.2010, 15:06
Новичок

Отправить личное сообщение для AlexeyGL Посмотреть профиль Найти все сообщения от AlexeyGL
 
Регистрация: 02.04.2010
Сообщений: 2

Двумерная упаковка 7 деталей
Доброго времени суток! Нуждаюсь в помощи в решении следующей задачи с acm.bsu.by:

Условие
Петя и Вася очень любят решать говололомки. Однажды, воскресным утром они собрались вместе и долго думали какую же говололомку им порешать. Они уже разгадали не одну сотню японский кросвордов, судоку и других подобных задач. И тут Петя придумал новую задачу. Он достал из полки старую бумагу для вырезаний, которая осталась у него еще с детского садика и они с Васей захотели уложить их в прямоугольник минимальной площади. Они долго ломали голову как это сделать и к вечеру поняли, что лучше бы им упростить задачу. Для этого они установили в ней ограничение, что прямоугольники могут располагаться только параллельно осям координат (включая прямоугольник минимальной прощади, в который они хотят вставить все эти прямоугольники). Дело было вечером и поэтому Вася и Петя разошлись по домам, но напоследок поспорили, кто же быстрее разложит 7 прямоугольников в прямоугольник минимальной площади. Они договорились о размерах этих 7 прямоугольниках. Помогите Пете решить эту непосильную задачу. Так же Петя понял, что возможно, что Вася захочет реванш, поэтому он хочет получить программу, которая находила бы расстановку для любых размеров, а не только тех, о которых он договорился с Васей в воскресный вечер.

Для заданных размеров прямоугольников необходимо определить минимальную площадь прямоугольника, в который влезут эти прямоугольники.

Входные данные
Входные данные находятся в текстовом файле с именем input.txt и имеют следующую структуру: в каждой строке (всего их 7) имеется по 2 целых числа w и h (0≤w, h≤100) , задающие размеры прямоугольников.

Выходные данные
Выходные данные должны быть записаны в текстовый файл с именем output.txt и иметь следующий формат: в первой строке записано целое число - минимальная площадь прямоугольника, в который можно уложить данные прямоугольники.

Пример входных данных
5 3
8 2
3 4
1 6
5 3
8 4
3 5

Пример выходных данных
114



Время на тест - 15сек.
Задача из раздела "Перебор", так что эвристикой похоже не обойтись. Уже перелапатил пол инета (буржуйского в том числе) - не могу ничего поделать. Попробовал упаковывать в полосу фикс. высоты (варьируя высотой) - т.к. алгоритм выдаёт не всегда оптимал - то прошло только 2 из 5 тестов, причём 2 из 3 оставшихся не прошло по времени, а 1 - вывел неправильный ответ. К преподу подходил - сказал осуществить полный перебор. Не могу понять как это сделать.

Если не трудно - напишите по-подробней, как это можно сделать (в смысле тот самый перебор), может даже псевдо-кодом угастите! Заранее благодарю.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимальная упаковка гость Вычислительная геометрия 3 26.03.2009 12:08