Блог

У меня есть большой прямоугольник, бумага, которую нужно разрезать на более мелкие. И у меня есть список необходимых размеров, ширина и высота бумаги меньшего размера. Список постоянно меняется.

Допустим, у меня есть бумага 4х4, и у меня есть 3 запроса в списке: 3х3, 2х4, 4х2

Если я сокращу на 3×3, остаток нельзя будет использовать для других запросов, поэтому я много трачу впустую.

Если я разрежу два 2х4 и 4х2, отходов не будет.

Мне нужно найти алгоритм для резки большой бумаги, чтобы отходы были наименьшими.

Я знаю, что это может быть сложно, я думаю перечислить все возможные перестановки, но это слишком дорого. Есть ли лучший алгоритм для решения такого рода проблем? Спасибо!