Простенькая задачка
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [216.73.216.88] |
|
|
правила раздела Алгоритмы

Простенькая задачка
|
Сообщ.
#1
,
|
|
|
|
Доброго времени суток, вам.
Тут возникла обна задача, как распились плиты ДСП что бы отходов было поменьше. Сформулировать задачу можно так: Имеются разные прямоугольники со сторонами a[i]<b[i], их N штук. (N-большое, возможны группы a*b) Надо разместить их на минимальном количестве листов размером LA<LB, при условии что кажды a[i]*b[i] "влазит" в LA*LB. При размещение прямоугольника на лист, лист режится по вертикали, затем по горизонтали или на оборот. В результате получается 3 прямоугольника нужный и два других, которые можно резать дальше. При недостатке места берётся ещё один лист. Вопрос как решать эту задачу. Может у кого есть какие гениальные или просто светлые идеии. Жду советов, ответов, ц.у. (PS: Простой рекурсивный перебор слишком долго что-то вроде O(M*4^N*N!) где M кол-во листов. Минимальное кол-во листов Mmin=round_up(Sum(a[i]*b[i])/(LA*LB)), максимальное соответственно Mmax=N) |
|
Сообщ.
#2
,
|
|
|
|
А такого типа задачи все NP-сложные. Поищи в инете материалы по "задача о рюкзаке".
Можно использовать эвристики. |