Ресурсы для оптимизации схем раскроя?

У меня есть куча прямоугольников разных размеров, которые мне нужно вырезать из куска листа.

Я хорошо знаком с python, но никогда не делал ничего подобного. Это похоже на проблему, которую раньше следовало исследовать с вычислительной точки зрения, но мне трудно найти какие-либо ресурсы.

Это классическая проблема, какие рекомендации по алгоритмам мне стоит изучить?


person Chris    schedule 11.09.2012    source источник
comment
эй, Крис, почему бы тебе не взглянуть на это? stackoverflow .com / questions / 3516044 /   -  person im so confused    schedule 12.09.2012
comment
у вас должно быть время гораздо проще, чем у того бедолаги, который имел дело с произвольной базовой формой. Вы, с другой стороны, ограничены большим прямоугольником (я полагаю), гарантируя, что оптимальное решение может быть найдено в разумные сроки (интуитивный инстинкт, никаких доказательств)   -  person im so confused    schedule 12.09.2012
comment
Проблема, которую вы описываете, представляет собой двухмерную версию задачи об упаковке бункера. @Akshaya дал вам одну ссылку. Выполните поиск в Google, и вы найдете гораздо больше.   -  person James Thiele    schedule 12.09.2012
comment
Думаю, @JamesThiele очень близок. Это: en.wikipedia.org/wiki/Cutting_stock_problem может быть более точно связано с вашей проблемой ( сведение сложной задачи NP к задаче линейного программирования)   -  person im so confused    schedule 12.09.2012