Здравствуйте всем! Недавно столкнулся с такой задачей.
На завод поступают брёвна различных диаметров. У нас есть несколько размеров досок(высота х ширина). Некоторые из них основные, а некоторые побочные. Нам нужно более менее оптимально распилить бревно(нужно учитывать, что пропил между досками тоже нужно оставлять; а длина досок не должна учитываться). Более формально: у нас есть круг, нам нужно оптимально разместить там заданные прямоугольники.
Подумав, я не придумал ничего кроме какого- то не очень оптимального и не очень хорошего перебора.
Подскажите пожалуйста что тут можно сделать.
Пожалуйста, укажите источник задачи.
Меня просто попросили написать такой кусок кода. Видимо какой- то проект собираются сделать. Поэтому у задачи скорее всего нет первоначального источника.
Что значит "оптимально"? Фиксирован ли радиус круга? Что значит "пропил между досками надо оставлять"? Можно ли вращить прямоугольники или же их стороны должны быть параллельны осям координат (и можно ли в таком случае вращать на 90 градусов)?
Пожалуй, самый важный вопрос — первый. Если хотим минимизировать неиспользуемую площадь — это одно, если хотим наставить туда как можно больше прямоугольников — это другое.
Это неточная задача. Я думаю что нужно напилить несколько вариантов(в одном площадь больше, в другом больше всего доски одного вида, или ещё что- нибудь)
Стороны должны быть параллельны осям.
Вращать на 90 градусов можно.
оставить пропил надо под толщину диска
Можно собрать призовой фонд и дать задачу на марафон.
А если серьезно — такие задачи можно и нужно решать эвристиками. Мне сразу приходит на ум идея: прижать один прямоугольник двумя точками к окружности, задав таким образом направления осей координат. Далее следует ставить все прямоугольники параллельно осям, причем так, чтобы каждый свежий прямоугольник нельзя было сдвинуть по крайней мере в две стороны. Итого получаем приемлемый по сложности переборчик.
О! Надо попробовать. Спасибо)