Обычно не очень положительно отношусь к подобного рода штукам в эфире, но тут, мне показалось, что может кому-то быть интересным.
Надо как-то решить следующую задачу:
Даны: основные прямоугольные листы размера a на b в количестве равном n, m заказов, также прямоугольников, характеризующихся своими габаритами, и количеством, в котором они должны быть исполнены. Мы должны размещать листы заказов на основном листе. Все листы заказов по своей максимальной характеристике размера меньше максимальной для основного листа и вообще любой заказ помещается на основной лист.
Требуется: расположить листы заказов на основном листе следующим образом:
1) Чтобы минимизировать количество используемых основных листов (чтобы их было меньше n для начала).
Требуется: расположить листы заказов на основном листе следующим образом:
1) Чтобы минимизировать количество используемых основных листов (чтобы их было меньше n для начала).
2) Чтобы количество различных конфигураций заполнения основных листов тоже было "достаточно близким к минимуму".
3) Допускается небольшое перевыполнение плана, когда какого-то конкретного заказа напечатано чуть больше, чем надо.
Задача не требует идеальных решений, да и их существования сомнительно для меня. Количество заказов достаточно мало (исчисляется количеством пальцев на паре рук), а размеры не больше максимального количества миллиметров в формате А3, первые два условия не перечислены в порядке предпочтительности. В наличие каких-то глобальных оптимумов, как я уже сказал, я слабо верю. Думал над жадностью, дп, переборами, ничего толкового пока в голову не пришло, что было бы можно назвать "нормальным" решением .
Было бы интересно услышать ваши мысли по этому поводу :)
Было бы интересно услышать ваши мысли по этому поводу :)
Причём программа защищена на нескольких уровнях - вплоть до ключа на LPT-порту.
Так что эта задачка - очень и очень хороший стимул финансово подняться.
Если у кого-то есть идеи - ищите сразу с кем заключать контракт. (это без шуток и на полном серьёзе)
In english your problem is called Cutting Stock Problem,
For general Information check http://en.wikipedia.org/wiki/Cutting_stock_problem.
Most existing solutions use some heuristics or genetic algorithms.
For example,see http://sourceforge.net/projects/cuttingproblem
Another interesting way is to use some prolog extensions which allow to solve optimization problems.
(The main idea of them is that you describe you problem in prolog and add optimization parameters )
Google something like "optimization problems weak constraints ".
For example,this solver may help:
http://www.dlvsystem.com/dlvsystem/html/DLV_User_Manual.html#AEN452
But it is still under development and it's syntax is not perfect.
I hope some of this will be helpful.