Полный перебор или есть другие варианты?

[androidvsu]

Имеется задача

Разрезать прямоугольник размера X*Y на детали прямоугольной формы размера X1*Y1 и X2*Y2, чтобы отходы были минимальны

Она решается полным перебором или есть более оптимальный вариант?

[androidvsu]

Не обязательно алгоритм, можно ссылку на теорию или хотя бы рассуждения - как лучше реализовать

[Тупой]

Не очень понятна постановка задачи. Что такое Х1, Х2, Y1, Y2? Что такое отходы? Если это прямоугольник минус два новых, то можно сделать так, чтобы отходы = 0 (по площади). Ну, короче, распишите, что конкретно сделать надо.

[JTG]

Гугли 'алгоритм раскроя фанеры', там есть быстрые эвристические методы, они дают 'оптимальный' результат с заданной вероятностью, перебором такое скорее всего не решить

[androidvsu]

Сообщение от Тупой

Не очень понятна постановка задачи. Что такое Х1, Х2, Y1, Y2? Что такое отходы? Если это прямоугольник минус два новых, то можно сделать так, чтобы отходы = 0 (по площади). Ну, короче, распишите, что конкретно сделать надо.

Х1, Х2, Y1, Y2 - размеры прямоугольников, на которые будет разрезаться исходный(X*Y)
отходы - в результате разрезания, может произойти так, что останутся куски, из которых уже нельзя никаким образом вырезать какую-либо деталь( или прямоугольник), и вот эти куски по площади нужно минимизировать!

[Тупой]

А если распилить фанеру на 2 части, то отходов вообще не будет. В чем проблема то?

[androidvsu]

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

[NeshSoft]

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

[androidvsu]

Сообщение от NeshSoft

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

А по делу можно ?...