|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.11.2012, 11:03 | #1 |
Пользователь
Регистрация: 27.06.2012
Сообщений: 38
|
Упаковка прямоугольников
Привет всем!
Вышла задача для которой никак не могу придумать структуру данных Даны четыре прямоугольника, т.е. файл в котором есть четыре строки в каждой строке два числа определяющие стороны прямоугольника. Требуется упаковать их в один прямоугольник с минимальной площадью, так чтобы прямоугольники не должны прикрывать друг друга. При упаковке можно поворачить прямоугольники на 90 градусов. Пример ввода данных 1 2 2 3 3 4 4 5 Пример вывода 4 10 5 8 Нужно вывести стороны образовавшегося прямоугольника, если решений несколько вывести все. Никак не могу найти для этого структуру данных Пробовал так. Код:
прямоугольники как следует. Пробовал представить каждый прямоугольник в виде матрицы, но код получился громоздким и не понятным, тем более нужно было при объединении освобождать одну матрицу а потом выделять другую чтобы оба прямоугольника поместились. И в конце концов отчаяся до такой степени что решил вот так вот нагло просить у вас помощи . Помогите пожалуйста, или хотя бы подскажите куда копать, может есть какая нибудь документация или статья. Последний раз редактировалось monster-bonster; 22.11.2012 в 11:06. |
22.11.2012, 11:30 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
проблема в том, что Вам нужно думать над АЛГОРИТМОМ решения,
а Вы думаете над тем, как отобразить прямоугольники в программе (т.е. над второстепенными техническими деталями... Думайте над алгоритмом. (вот, представьте, вам дали 10 прямоугольников (из картона). Как бы Вы находили варианты решения (просто, ручками, на столе, без компьютера)?... p.s. я с налёта красивого алгоритма решения не вижу.. Очевидно, что полученный в результате не может иметь сторону, меньше, сумма сторон некоторых исходных прямоугольников.. Но другого варианта, как полный перебор всех возможных размещений я не вижу... |
22.11.2012, 11:34 | #3 |
Пользователь
Регистрация: 27.06.2012
Сообщений: 38
|
Вы правы, но ведь прежде чем реализовать алгоритм перебора
вариантов, нужно организовать структуру данных, функции, которые работают над ним (объединяют, поворачивают и т. д.). Алгоритм перебора я реализую без проблем, но ведь как я сказал алгоритм не проблема, но вот структура данных ни как не складывается. |
22.11.2012, 12:21 | #4 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
Насчёт алгоритма... вероятно, следует идти по площадям от суммарной площади прямоугольников и проверять, заполняется или нет. Площади, у которых один из множителей всегда меньше максимума из минимальных сторон, можно отбрасывать сразу. |
|
22.11.2012, 13:09 | #5 | |
С++
Форумчанин
Регистрация: 22.09.2008
Сообщений: 791
|
Цитата:
monster-bonster, Abstraction прав, подумайте, добавьте необходимые методы и все будет отлично
Форматируйте код, будьте людьми.
|
|
22.11.2012, 13:13 | #6 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
нашел похожую задачу на винграде..
если интересно, то тут обсуждение ( и полезные ссылки!): набор прямоугольников вписать в мин прямоугольник |
22.11.2012, 13:23 | #7 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
|
|
22.11.2012, 14:12 | #8 | |
С++
Форумчанин
Регистрация: 22.09.2008
Сообщений: 791
|
Цитата:
Форматируйте код, будьте людьми.
|
|
25.11.2012, 13:07 | #9 |
Пользователь
Регистрация: 27.06.2012
Сообщений: 38
|
Я бы рад использовать классы, но я должен
решить эту задачу на компиляторе gnu c. Пожалуйста если это вас не затруднит, определите решение более специфично, а то вы так поверхностно объясняете. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Упаковка структур | ds.Dante | Общие вопросы .NET | 0 | 15.02.2012 16:47 |
3D упаковка | elpilasgsm | Помощь студентам | 0 | 06.11.2011 00:22 |
Упаковка программы | daimon7777 | Помощь студентам | 8 | 03.03.2011 18:44 |
Упаковка БД | Serge77 | БД в Delphi | 1 | 02.06.2009 11:58 |