<?xml version='1.0' encoding="utf-8"?>
      <rss version='2.0'>
      <channel>
      <title>Форум на Исходниках.RU</title>
      <link>https://forum.sources.ru</link>
      <description>Форум на Исходниках.RU</description>
      <generator>Форум на Исходниках.RU</generator>
  	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=9136&amp;view=findpost&amp;p=89737</guid>
        <pubDate>Fri, 03 Oct 2003 14:27:25 +0000</pubDate>
        <title>Простенькая задачка</title>
        <link>https://forum.sources.ru/index.php?showtopic=9136&amp;view=findpost&amp;p=89737</link>
        <description><![CDATA[Visitor: А такого типа задачи все NP-сложные. Поищи в инете материалы по &quot;задача о рюкзаке&quot;.<br>Можно использовать эвристики.<br><br>]]></description>
        <author>Visitor</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=9136&amp;view=findpost&amp;p=89736</guid>
        <pubDate>Fri, 03 Oct 2003 12:44:15 +0000</pubDate>
        <title>Простенькая задачка</title>
        <link>https://forum.sources.ru/index.php?showtopic=9136&amp;view=findpost&amp;p=89736</link>
        <description><![CDATA[Serg_K: Доброго времени суток, вам.<br><br>Тут возникла обна задача, как распились плиты ДСП что бы отходов<br>было поменьше.<br><br>Сформулировать задачу можно так:<br> Имеются разные прямоугольники со сторонами a[i]&lt;b[i], их N штук. (N-большое,<br>возможны группы a*b) Надо разместить их на минимальном количестве листов <br>размером LA&lt;LB, при условии что кажды a[i]*b[i] &quot;влазит&quot; в LA*LB.<br> При размещение прямоугольника на лист, лист режится по вертикали,<br>затем по горизонтали или на оборот. В результате получается 3<br>прямоугольника нужный и два других, которые можно резать дальше.<br>При недостатке места берётся ещё один лист.<br> Вопрос как решать эту задачу. Может у кого есть какие гениальные <br>или просто светлые идеии. Жду советов, ответов, ц.у.<br><br>(PS: Простой рекурсивный перебор слишком долго что-то вроде O(M*4^N*N!)<br>где M кол-во листов. <br>Минимальное кол-во листов Mmin=round_up(Sum(a[i]*b[i])/(LA*LB)),<br>максимальное соответственно Mmax=N)<br><br><br>]]></description>
        <author>Serg_K</author>
        <category>Алгоритмы</category>
      </item>
	
      </channel>
      </rss>
	