Разместить максимальное количество прямоугольников на листе! - Общие вопросы Delphi

Armageddets · 31.05.2017, 22:46

Всем доброго времени суток, уважаемые эксперты. Передо мной стоит следующая задача:

Написать программу, в которой. Вводится размер листа, количество разных прямоугольников и их размеры. Требуется по нажатию на кнопку расположить на выбранном размере листа максимальное количество этих фигур (прямоугольников, размеры, которых нами введены).

Задачи типа "вместить разные фигуры на поле" я уже делал. А вот как оптимально расположить максимально возможное количество требуемых прямоугольников не совсем понимаю.

Подскажите в какую сторону копать, может есть какие-то алгоритмы для этого? Или только обычным перебором все расставлять и сравнивать между собой?

Vasyl2 · 31.05.2017, 22:53

Это NP-сложная задача. Почитай - https://en.wikipedia.org/wiki/Bin_packing_problem

Программы для оптимальной раскройки с тем же сталкиваются.

31.05.2017, 22:46	#1
Armageddets Форумчанин Регистрация: 30.06.2012 Сообщений: 145	Разместить максимальное количество прямоугольников на листе! Всем доброго времени суток, уважаемые эксперты. Передо мной стоит следующая задача: Написать программу, в которой. Вводится размер листа, количество разных прямоугольников и их размеры. Требуется по нажатию на кнопку расположить на выбранном размере листа максимальное количество этих фигур (прямоугольников, размеры, которых нами введены). Задачи типа "вместить разные фигуры на поле" я уже делал. А вот как оптимально расположить максимально возможное количество требуемых прямоугольников не совсем понимаю. Подскажите в какую сторону копать, может есть какие-то алгоритмы для этого? Или только обычным перебором все расставлять и сравнивать между собой?

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Как определить отрезок, пересекающий наибольшее количество прямоугольников	Daniel0K	Паскаль, Turbo Pascal, PascalABC.NET	4	17.02.2013 18:00
Двумерный массив. Определить количество прямоугольников образованных числом 1.	alekcey0211	Паскаль, Turbo Pascal, PascalABC.NET	2	28.11.2012 17:03
Java а квадратном клетчатом листе бумаги размерами 100х100 нарисовано несколько прямоугольников. подсчитать сколько.	Marisa21	Помощь студентам	1	20.06.2011 05:41
Подсчет рандомных прямоугольников на листе бумаги	Junk1E	Общие вопросы C/C++	1	10.12.2009 23:03
Как создать кнопки с ссылками на другие листы Excel 2007 и разместить их на отдельном листе?	footman	Microsoft Office Excel	0	21.07.2009 00:21

31.05.2017, 22:53	#2
Vasyl2 Новичок Джуниор Регистрация: 31.05.2017 Сообщений: 1	Это NP-сложная задача. Почитай - https://en.wikipedia.org/wiki/Bin_packing_problem Программы для оптимальной раскройки с тем же сталкиваются.