В общем виде это NP-полная
ИмхоДом › Форумы › планирование › Он — лайн сервис по экономному раскрою? › В общем виде это NP-полная
В общем виде это NP-полная задача о раскрое. Добро пожаловать в волшебный мир линейного программирования
ru.wikipedia.org/wiki/Задача_раскроя
поминтся, на курсовой перебором делал, была типичная задача по раскрою листов фанеры на прямоугольники. но у меня ещё была база знаний: прогнозирование потребностей кусков определенного размера в будущем и склад остатков-кусочков (экономическая составляющая — насколько выгодно держать склад остатков-кусочков, какие куски выгодней утилизировать, а не сохранять)…
честно пытался использовать всякие комбинаторики, которых нас учили, прогнозирование и тому подобное. но с экономической точки зрения банальный перебор оказывался наиболее эффективным и утилизация довольно больших кусков фанеры, т.к. юнит-тесты показывали чрезмерное захламление склада кусочками различной "удобной" размерности, что сильно усложняет складирование и для дешевых материалов не выгодно.
из лекции
"представьте — у вас есть эластичная ёмкость заданного объёма, с заданными коэфициентами растягивания по различным осям. и есть набор фигур неправильной формы, которые нужно оптимально скомпоновать друг с другом так, чтобы в ёмкость их поместилась максимальное кол-во. Как решить эту задачу? она не по силам современным супер-компьютерам, но вполне по силам деревенскому мужику: ёмкость — это мешок, фигуры — картошка. Мужик насыпает в мешок картошку, трясёт его, досыпает сколько получится и завязывает. мужика не интересует достижение максимальной вместимости мешка, ему нужна оптимальная, экономически оправданная вместимость. без 5-секундной встряски ему понадобится 70 мешков, с встряской — 60, с максимально компактным распределением картошки — 50 мешков. Разница каждый раз в 10 мешков ценою в надцать сотен рублей. Но меджу первым и вторым способом времязатраты будут 50+ секунд, а между вторым и третьим — тысячи лет в лучшем случае."