Гюльчатай, раскрой листика.
Есть для обсуждения пара прикладных задач, почти реально производственных.
1. Из прямоугольного листа материала размера х*у требуется вырезать наибольшее возможное число n прямоугольников размера a*b. (x, y, a, b заданы, n -> max)
Разрезы должны быть параллельны сторонам разрезаемого прямоугольника.
В качестве тестового примера: из листа 5*5 можно вырезать 4 прямоугольника 3*2 (а в серединке останется дырочка). Нужен хоть какой-нибудь внятный алгоритм.
"Двойственная" задача.
2. Есть длинная лента материала шириной х. Требуется отрезать от нее прямоугольный кусок наименьшей длины y так, чтобы из него можно было вырезать n прямоугольников размера a*b. (x, n, a, b заданы, у -> min)
1. Из прямоугольного листа материала размера х*у требуется вырезать наибольшее возможное число n прямоугольников размера a*b. (x, y, a, b заданы, n -> max)
Разрезы должны быть параллельны сторонам разрезаемого прямоугольника.
В качестве тестового примера: из листа 5*5 можно вырезать 4 прямоугольника 3*2 (а в серединке останется дырочка). Нужен хоть какой-нибудь внятный алгоритм.
"Двойственная" задача.
2. Есть длинная лента материала шириной х. Требуется отрезать от нее прямоугольный кусок наименьшей длины y так, чтобы из него можно было вырезать n прямоугольников размера a*b. (x, n, a, b заданы, у -> min)