Учитывая прямоугольник произвольного размера, я хочу упаковать его в прямоугольники фиксированного размера, чем меньше, тем лучше.
Чтобы сделать это возможным, входной прямоугольник можно разрезать на более мелкие части, прежде чем он будет упакован вместе. Резка возможна только при кратных фиксированному целому числу a , и количество сокращений должно быть разумным.
Например, это бесполезное решение - всегда разрезать на * квадраты и просто упаковать их вместе, а затем добавить оставшиеся меньшие блоки ( a * x, y * a и y * a , где x <<em> a , y <<em> a ).
Хотя эффективность упаковки была бы довольно хорошей, количество порезов может быть неприемлемым.
Это в значительной степени сводится к проблеме упаковки 2-мерных бункеров, когда упаковываемые прямоугольники будут разрезаться на части в определенных местах, если это приведет к повышению эффективности упаковки. Я знаю, что есть много ресурсов по проблеме упаковки в мусорное ведро, но я не нашел ничего, что включало бы разбиение на более мелкие прямоугольники перед упаковкой.
Есть ли какие-либо ресурсы по этой или хотя бы аналогичной проблеме, доступной где-нибудь? Любые идеи о том, как реализовать алгоритм для этого, кроме грубого принуждения, также будут высоко оценены (конечно, я не ищу алгоритм, который дает оптимальные результаты, но достаточно близкий).