На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Простенькая задачка
    Доброго времени суток, вам.

    Тут возникла обна задача, как распились плиты ДСП что бы отходов
    было поменьше.

    Сформулировать задачу можно так:
    Имеются разные прямоугольники со сторонами 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)


      А такого типа задачи все NP-сложные. Поищи в инете материалы по "задача о рюкзаке".
      Можно использовать эвристики.

      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
      0 пользователей:


      Рейтинг@Mail.ru
      [ Script execution time: 0.1421 ]   [ 15 queries used ]   [ Generated: 22.11.26, 18:09 GMT ]