{"id":160869,"date":"2012-12-17T00:11:03","date_gmt":"2012-12-16T20:11:03","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=160869"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=160869","title":{"rendered":"<span class=\"post_title\">\u041f\u0440\u043e \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u0443\u044e \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0443: online \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b<\/span>"},"content":{"rendered":"<div class=\"content html_format\">   \t<img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/c94\/07d\/b77\/c9407db7753a73de4241c3f908049528.jpg\" align=\"right\"\/>\u042d\u0442\u043e \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0435\u043d\u0438\u0435 <a href=\"http:\/\/habrahabr.ru\/post\/136225\/\">\u043f\u043e\u0441\u0442\u0430<\/a> \u043f\u0440\u043e \u043e\u0444\u0444\u043b\u0430\u0439\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438.<\/p>\n<p>  \u0421\u0443\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0438: \u0438\u043c\u0435\u0435\u043c \u043f\u043e\u043b\u0443\u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u0443\u044e \u043f\u043e\u043b\u043e\u0441\u0443 \u2014 \u043a\u0430\u043a \u0432 \u0442\u0435\u0442\u0440\u0438\u0441\u0435, \u0442\u043e\u043b\u044c\u043a\u043e \u0431\u0435\u0437 game over&#8217;\u0430, \u0438 \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432. \u0414\u0430\u043d\u043d\u044b\u0435 \u043e \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430\u0445 \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u044e\u0442 \u0432 \u0440\u0435\u0436\u0438\u043c\u0435 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438; \u043a\u0430\u0436\u0434\u044b\u0439 \u043d\u043e\u0432\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0435\u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0440\u0430\u0437\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0435 \u0434\u0432\u0438\u0433\u0430\u0442\u044c \u0441 \u043c\u0435\u0441\u0442\u0430. \u0426\u0435\u043b\u044c \u2014 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043e\u0431\u0449\u0443\u044e \u0432\u044b\u0441\u043e\u0442\u0443 \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432.<br \/>  \u042d\u0442\u043e online-\u0432\u0430\u0440\u0438\u0430\u0446\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u0431 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0435 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432 \u0432 \u043f\u043e\u043b\u0443\u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u0443\u044e \u043f\u043e\u043b\u043e\u0441\u0443 (2 Dimensional Strip Packing, 2DSP).<\/p>\n<p>  \u0427\u0443\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0441\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435, \u0430 \u043f\u043e\u043a\u0430, \u0431\u0435\u0437 \u043b\u0438\u0448\u043d\u0438\u0445 \u0441\u043b\u043e\u0432, \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c.<br \/>  <a name=\"habracut\"><\/a><br \/>  \u0414\u043b\u044f \u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0432\u043e\u0442 \u0442\u0430\u043a\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043a\u0438\u0440\u043f\u0438\u0447\u0435\u0439:<br \/>  <img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/a6f\/cc9\/adf\/a6fcc9adffcd9955dd55d55ce6257dec.png\"\/><br \/>  (\u0421\u043f\u043e\u043d\u0441\u043e\u0440 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u2014 random.org).<br \/>  \u0411\u0443\u0434\u0443\u0442 \u043e\u043f\u0438\u0441\u0430\u043d\u044b \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043e\u0431\u0449\u0430\u044f \u0438\u0434\u0435\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u043f\u043e\u043b\u043e\u0441\u0443 \u043d\u0430 \u043e\u0431\u043b\u0430\u0441\u0442\u0438, \u0438 \u0440\u0430\u0437\u043c\u0435\u0449\u0430\u0442\u044c \u0432\u043d\u043e\u0432\u044c \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u044e\u0449\u0438\u0435 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0438 \u0432 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u043c \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u044f\u043c.<\/p>\n<h2>Level algorithms<\/h2>\n<p><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/84c\/3f9\/ad9\/84c3f9ad9feb9931fe9a4c3b8f84fbe0.png\" align=\"right\"\/><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/b4b\/19c\/924\/b4b19c92465eb2b5c5dcb3a09720d994.png\" align=\"right\"\/><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/fe4\/343\/1a0\/fe43431a06d9aa33cd76d36afc787381.png\" align=\"right\"\/><br \/>  \u041f\u043e\u0434\u0445\u043e\u0434 \u0432\u0441\u0435\u0445 \u0443\u0440\u043e\u0432\u043d\u0435\u0432\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u043e\u043b\u043e\u0441\u0430 \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0438, \u0438\u0441\u0445\u043e\u0434\u044f \u0438\u0437 \u0432\u044b\u0441\u043e\u0442\u044b \u0438\u043c\u0435\u044e\u0449\u0438\u0445\u0441\u044f \u043d\u0430 \u0434\u0430\u043d\u043d\u043e\u043c \u044d\u0442\u0430\u043f\u0435 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432. \u041f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0438 \u0440\u0430\u0437\u043c\u0435\u0449\u0430\u044e\u0442\u0441\u044f \u0432\u0434\u043e\u043b\u044c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u043f\u043e\u043a\u0430 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e; \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u043b\u0441\u044f, \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c. \u0412\u044b\u0441\u043e\u0442\u0430 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u0441\u0430\u043c\u043e\u043c\u0443 \u0432\u044b\u0441\u043e\u043a\u043e\u043c\u0443 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0443 \u0432 \u043d\u0435\u043c. \u0412\u043e\u0442 \u0442\u0440\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438:<br \/>  Next Fit Level \u2014 \u043a\u043e\u0433\u0434\u0430 \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c, \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u00ab\u0437\u0430\u043a\u0440\u044b\u0432\u0430\u0435\u0442\u0441\u044f\u00bb \u0438 \u0435\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c;<br \/>  First Fit Level \u2014 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u0440\u043e\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f <i>\u043a\u0430\u0436\u0434\u044b\u0439<\/i> \u0443\u0440\u043e\u0432\u0435\u043d\u044c, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u0441\u0430\u043c\u043e\u0433\u043e \u043d\u0438\u0436\u043d\u0435\u0433\u043e, \u0438 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0439, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043c\u0435\u0441\u0442\u0430;<br \/>  Best Fit Level \u2014 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u0440\u043e\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f <i>\u0432\u0441\u0435<\/i> \u0443\u0440\u043e\u0432\u043d\u0438, \u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0439 \u2014 \u0442\u043e\u0442, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043f\u043e\u0441\u043b\u0435 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u043c\u0435\u0441\u0442\u0430.<br \/>  \u0412\u0441\u0435 \u0442\u0440\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u0440\u043e\u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0432\u044b\u0448\u0435. \u041d\u0430 \u044d\u0442\u043e\u043c \u044d\u0442\u0430\u043f\u0435 \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u043e \u0434\u043e\u0433\u0430\u0434\u0430\u0442\u044c\u0441\u044f, \u043a\u0430\u043a\u043e\u0439 \u0433\u0434\u0435.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b NFL, FFL, BFL<\/b><\/p>\n<div class=\"spoiler_text\"><b>Next Fit Level<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W. Output: The height H and the entire packing.  1: level = 0; h(level + 1) = 0; H = 0; i = 0  2: while there is an unpacked rectangle do  3:    i++  4:    if there is sufficient space on current level then  5:       pack rectangle left justified  6:       if h(level + 1) &lt; h(Li) then  7:          h(level + 1) = h(Li)  8:       end if  9:    else [there is insufficient space on current level] 10:       open a new level and pack the rectangle 11:       H += h(level + 1); level++ 12:    end if 13: end while 14: print H and entire packing<\/pre>\n<p>  <b>First Fit Level<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W. Output: The height H and the entire packing.  1: level = 0; h(level + 1) = h(L1); H = h(L1); i = 1  2: while there is an unpacked rectangle do  3:    i++; level = 0  4:    search for the lowest level with sufficient space  5:    if such a level exists then  6:       pack rectangle left justified  7:       if this is the top-most level and h(level) &lt; h(Li) then  8:          h(level) = h(Li)  9:       end if 10:    else [there is insufficient space in all existing levels] 11:       create a new level above the top-most level 12:       pack rectangle left justified 13:       h(level) = h(Li); H += h(Li) 14:    end if 15: end while 16: print H and entire packing<\/pre>\n<p>  <b>Best Fit Level<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W. Output: The height H and the entire packing.  1: level = 0; h(level + 1) = h(L1); H = h(L1); i = 0  2: while there is an unpacked rectangle do  3:    i++; level = 0  4:    search for lowest level with minimum residual horizontal space  5:    if such a level exists then  6:       pack rectangle left justified  7:    else [such a level does not exist]  8:       create a new level above the top-most level  9:       pack rectangle left justified 10:       h(level) = h(Li); H += h(Li) 11:    end if 12: end while 13: print H and entire packing<\/pre>\n<\/div>\n<\/div>\n<h2>Bi-Level Next Fit<\/h2>\n<p><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/bbd\/f46\/5a3\/bbdf465a318ab5d325ee02717c262a4d.png\" align=\"right\"\/><br \/>  \u0425\u0438\u0442\u0440\u0430\u044f \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f Next Fit Level. \u0423\u0440\u043e\u0432\u043d\u0438 \u0441\u043e\u0437\u0434\u0430\u044e\u0442\u0441\u044f \u043f\u043e \u0434\u0432\u0430, \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u0432\u043e\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f.<br \/>  \u041d\u0438\u0436\u043d\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c (\u0438\u043b\u0438 \u0432\u0441\u0435 \u043d\u0435\u0447\u0435\u0442\u043d\u044b\u0435): \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u0440\u0438\u0448\u0435\u0434\u0448\u0438\u0439 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e \u043b\u0435\u0432\u043e\u043c\u0443 \u043a\u0440\u0430\u044e, \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u2014 \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e, \u043f\u043e\u043a\u0430 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043c\u0435\u0441\u0442\u0430. \u0417\u0430\u0442\u0435\u043c \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0437\u0430\u043a\u0440\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0438 \u0435\u0433\u043e \u0432\u044b\u0441\u043e\u0442\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u0441\u0430\u043c\u043e\u043c\u0443 \u0432\u044b\u0441\u043e\u043a\u043e\u043c\u0443 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0443 \u0432 \u043d\u0435\u043c.<br \/>  \u0412\u0435\u0440\u0445\u043d\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c (\u0438\u043b\u0438 \u0432\u0441\u0435 \u0447\u0435\u0442\u043d\u044b\u0435): \u0435\u0441\u043b\u0438 \u043d\u0430 \u043d\u0438\u0436\u043d\u0435\u043c \u0443\u0440\u043e\u0432\u043d\u0435 \u0432\u0441\u0435\u0433\u043e \u043e\u0434\u0438\u043d \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a, \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u043d\u0438\u0436\u043d\u0435\u043c\u0443. \u0415\u0441\u043b\u0438 \u0434\u0432\u0430 \u0438 \u0431\u043e\u043b\u044c\u0448\u0435, \u0442\u043e \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0434 \u0431\u043e\u043b\u0435\u0435 \u043d\u0438\u0437\u043a\u0438\u043c \u0438\u0437 \u0434\u0432\u0443\u0445 \u043f\u0440\u0438\u0436\u0430\u0442\u044b\u0445 \u043a \u043a\u0440\u0430\u044f\u043c \u043f\u043e\u043b\u043e\u0441\u044b, \u0438 \u0442\u0430\u043a\u0436\u0435 \u043f\u0440\u0438\u0436\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u043a \u043a\u0440\u0430\u044e \u043f\u043e\u043b\u043e\u0441\u044b; \u0432\u0441\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e, \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043e\u0442 \u0442\u043e\u0433\u043e, \u0433\u0434\u0435 \u0431\u044b\u043b \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u043d \u043f\u0435\u0440\u0432\u044b\u0439 \u2014 \u0441\u043b\u0435\u0432\u0430 \u0438\u043b\u0438 \u0441\u043f\u0440\u0430\u0432\u0430.<\/p>\n<p>  \u0417\u0432\u0443\u0447\u0438\u0442 \u043f\u0443\u0442\u0430\u043d\u043e \u0438 \u043d\u0435 \u0441\u0440\u0430\u0437\u0443 \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u043a \u0447\u0435\u043c\u0443 \u0442\u0430\u043a\u0438\u0435 \u0442\u0430\u043d\u0446\u044b \u0441 \u0431\u0443\u0431\u043d\u043e\u043c. \u0415\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435, \u0447\u0442\u043e \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442 \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u2014 \u044d\u0442\u043e \u0431\u043e\u043b\u0435\u0435 \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u043e\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432 \u043f\u043e \u043e\u0431\u044a\u0435\u043c\u0443 \u043f\u043e\u043b\u043e\u0441\u044b, \u0431\u0435\u0437 \u043f\u0435\u0440\u0435\u043a\u043e\u0441\u0430 \u043a \u043b\u0435\u0432\u043e\u043c\u0443 \u043a\u0440\u0430\u044e. \u041d\u043e \u043c\u044b \u0435\u0449\u0435 \u0432\u0435\u0440\u043d\u0435\u043c\u0441\u044f \u043a \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0438, \u043a\u043e\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043a\u043e\u043c\u043f\u0440\u0435\u0441\u0441\u0438\u0438.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c BiNFL<\/b><\/p>\n<div class=\"spoiler_text\"><b>Bi-Level Next Fit<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W. Output: The height H and the entire packing.  1: level = 1; h(level) = 0; H = 0; i = 1  2: open a new bi-level  3: call 'pack on lower level'  4: print H and entire packing Procedure 'pack on lower level'  1: the first rectangle packed is left justified  2: subsequent rectangles that fit are right justified  3: if there is insufficient space then  4:    h(level) is given by the height of tallest rectangle packed  5:    call 'pack on upper level'  6: end if Procedure 'pack on the upper level'  1: if Li+1 is the first rectangle packed then  2:    left justify on top of Li  3: else  4:    if Li+2 is the first rectangle packed then  5:       pack above min {h(Li); h(Li+1)}  6:       justify according to min {h(Li); h(Li+1)}  7:   else  8:      if Li+j (j &gt; 3) fits on the upper level then  9:         left justify all other rectangles 10:      else [rectangle does not fit] 11:         H += h(lower) + h(upper); open new bi-level 12:      end if 13:    end if 14: end if<\/pre>\n<\/div>\n<\/div>\n<h2>Shelf algorithms<\/h2>\n<p><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/e5e\/9dc\/47b\/e5e9dc47b99520d0c5634cb5fd531375.png\" align=\"right\"\/><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/9c8\/472\/192\/9c8472192307cda4705442917ef525c5.png\" align=\"right\"\/><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/635\/1d4\/db7\/6351d4db7b850924c94ffb03d5158590.png\" align=\"right\"\/><br \/>  \u0428\u0435\u043b\u044c\u0444\u043e\u0432\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043d\u0435 \u043f\u0440\u0438\u0432\u044f\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043a \u0442\u043e\u0447\u043d\u043e\u0439 \u0432\u044b\u0441\u043e\u0442\u0435 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432 \u0438 \u043f\u043e\u0441\u043b\u0435 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 (\u0448\u0435\u043b\u044c\u0444\u0435) \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430 \u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439 \u0435\u0441\u043b\u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0432\u044b\u0448\u0435. \u042d\u0442\u043e \u00ab\u043d\u0435\u043c\u043d\u043e\u0433\u043e\u00bb \u0440\u0435\u0433\u0443\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c <i>r<\/i>&nbsp;\u2208&nbsp;(0;1). \u0412\u044b\u0441\u043e\u0442\u0430 \u0448\u0435\u043b\u044c\u0444\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a <i>r<\/i><sup><i>k<\/i><\/sup>, \u0433\u0434\u0435 <i>r<\/i><sup><i>k+1<\/i><\/sup> &lt; h(L<sub>i<\/sub>) \u2264 <i>r<\/i><sup><i>k<\/i><\/sup> \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0446\u0435\u043b\u043e\u0433\u043e <i>k<\/i> \u0438 \u0432\u044b\u0441\u043e\u0442\u044b \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430 h(L<sub>i<\/sub>). \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0443\u0440\u043e\u0432\u043d\u0435\u0432\u044b\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c, \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0438 \u043e\u0431\u0445\u043e\u0434\u0430 \u0448\u0435\u043b\u044c\u0444\u043e\u0432 Next Fit, First Fit \u0438 Best Fit. \u041e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0435\u043b\u044c\u0444\u0435 \u00ab\u0440\u0435\u0437\u0435\u0440\u0432\u00bb \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u0432\u044b\u0433\u043e\u0434\u043d\u044b\u043c \u0432 \u0434\u0432\u0443\u0445 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 (\u0441\u0440\u0430\u0432\u043d\u0438\u0442\u0435 FFL \u0438 FFS, BFL \u0438 BFS). \u0412 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 <i>p<\/i>=0,7.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b NFS, FFS, BFS<\/b><\/p>\n<div class=\"spoiler_text\"><b>Next Fit Shelf<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)}        the parameter r and the strip width W. Output: The height H and the entire packing.  1: shelf = 1; w(shelf) = 0;     h(shelf) = r^k for some integer k; i = 0; H = h(shelf)  2: while there is an unpacked rectangle do  3:    i++; compute k  4:    if there is sufficient space and r^(k+1) &lt; h(Li) \u2264 r^k then  5:       pack rectangle to the right of the previously packed rectangle  6:    else [there is insufficient space]  7:       create a new shelf on top of the previous one           and pack rectangle Li on the new shelf.  8:       shelf++; H += r^k  9:    end if 10: end while 11: print H and entire packing.<\/pre>\n<p>  <b>First Fit Shelf<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)}        the parameter r and the strip width W. Output: The height H and the entire packing.  1: shelf = 1; h(shelf) = r^k for some integer k;     i = 0; H = h(shelf); shelfnum = 1  2: while there is an unpacked rectangle do  3:    i++; compute k  4:    search for lowest shelf of appropriate height with sufficient space  5:    if such a shelf exists then  6:       pack rectangle to the right of the previously packed rectangle  7:    else [there is insufficient space in all shelves of              appropriate height or such a shelf does not exist]  8:       create a new shelf above the top-most shelf           and pack rectangle Li on the new shelf.  9:       shelf++; H += r^k; shelfnum++ 10:    end if 11: end while 12: print H and entire packing.<\/pre>\n<p>  <b>Best Fit Shelf<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)}        the parameter r and the strip width W. Output: The height H and the entire packing.  1: shelf = 1; h(shelf) = r^k for some integer k;     i = 0; H = h(shelf); shelfnum = 1  2: while there is an unpacked rectangle do  3:    i++; compute k  4:    search all shelves (starting with the bottom) for one        with appropriate height and has minimum residual horizontal space.  5:    if such a shelf exists then  6:       pack rectangle to the right of the previously packed rectangle  7:    else [there is insufficient space or              there is no shelf of appropriate height]  8:       create a new shelf above the top-most shelf           and pack the rectangle Li on the new shelf.  9:       shelf++; H += r^k; shelfnum++ 10:    end if 11: end while 12: print H and entire packing.<\/pre>\n<\/div>\n<\/div>\n<h2>Harmonic Shelf<\/h2>\n<p><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/77b\/4a9\/c0f\/77b4a9c0fb8fccf72f5c79cc433ac1df.png\" align=\"right\"\/><br \/>  Harmonic Shelf \u043f\u0430\u043a\u0443\u0435\u0442 \u043d\u0430 \u043e\u0434\u0438\u043d \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0438 \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043e \u0441\u0445\u043e\u0436\u0435\u0439 \u0432\u044b\u0441\u043e\u0442\u043e\u0439, \u043d\u043e \u0438 \u0441\u043e \u0441\u0445\u043e\u0436\u0435\u0439 \u0448\u0438\u0440\u0438\u043d\u043e\u0439. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0431\u043e\u043b\u044c\u0448\u0435 \u0443\u0440\u043e\u0432\u043d\u0435\u0439, \u043d\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u044b \u043e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u043f\u043b\u043e\u0442\u043d\u0435\u0435. \u0412\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 <i>M<\/i> \u0434\u043b\u044f \u0440\u0430\u0441\u0447\u0435\u0442\u0430 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u043e\u0439 \u0448\u0438\u0440\u0438\u043d\u044b.<\/p>\n<p>  \u041e\u0431\u0449\u0430\u044f \u0448\u0438\u0440\u0438\u043d\u0430 \u043f\u043e\u043b\u043e\u0441\u044b, \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0432\u043e\u0437\u044c\u043c\u0435\u043c \u0435\u0435 \u0437\u0430 \u0435\u0434\u0438\u043d\u0438\u0446\u0443, \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043d\u0430 <i>M<\/i> \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432 <i>I<\/i><sub>1<\/sub>..<i>I<\/i><sub><i>M<\/i><\/sub>. \u0410\u0432\u0442\u043e\u0440 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442, \u0447\u0442\u043e \u0440\u0430\u0437\u0443\u043c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <i>M<\/i> \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 [3;&nbsp;12]. \u0428\u0438\u0440\u0438\u043d\u0430 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432 \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/aee\/47d\/375\/aee47d3755382a2fb46fcf9081ddcb2d.png\"\/>;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/b47\/e3f\/8ba\/b47e3f8badf98db52492675eb741141b.png\"\/><\/p>\n<p>  \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430 \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <i>p<\/i>. \u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 <i>k<\/i> \u0434\u043b\u044f \u0432\u044b\u0441\u043e\u0442\u044b \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0448\u0435\u043b\u044c\u0444\u043e\u0432\u044b\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c. \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u044e\u0442\u0441\u044f \u0434\u0432\u0430 \u0443\u0441\u043b\u043e\u0432\u0438\u044f: \u0435\u0441\u0442\u044c \u043b\u0438 \u0434\u043b\u044f \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430 \u043c\u0435\u0441\u0442\u043e \u043d\u0430 \u043a\u0430\u043a\u043e\u043c-\u043d\u0438\u0431\u0443\u0434\u044c \u0448\u0435\u043b\u044c\u0444\u0435 \u0432\u044b\u0441\u043e\u0442\u043e\u0439 <i>r<\/i><sup><i>k<\/i><\/sup> \u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043b\u0438 \u0435\u0433\u043e <i>p<\/i> \u0443\u0436\u0435 \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0442\u0430\u043c. \u0415\u0441\u043b\u0438 \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u043d\u043e \u043d\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e, \u0434\u043b\u044f \u043d\u0435\u0433\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u0442\u0441\u044f \u0441\u0432\u043e\u0439 \u0448\u0435\u043b\u044c\u0444, \u0441 \u0431\u043b\u0435\u043a\u0434\u0436\u0435\u043a\u043e\u043c \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u043a\u043e\u043c\u0444\u043e\u0440\u0442\u043d\u044b\u043c\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c\u0438. \u0412 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 <i>p<\/i>=0,7, <i>M<\/i>=4.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c HS<\/b><\/p>\n<div class=\"spoiler_text\"><b>Harmonic Shelf<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)}        the parameters M, r and the strip width W. Output: The height H and the entire packing.  1: shelf = 1; h(shelf) = r^k for some integer k; i = 0  2: while there is an unpacked rectangle do  3:    i++; compute k such that r^(k+1) &lt; h(Li) \u2264 r^k  4:    compute the value of p such that 1\/(p+1) &lt; w(Li) \u2264 1\/p        where 1 \u2264 p &lt; M  5:    amongst shelves of height r^k find the one        with packing rectangles whose width fits in the interval Ip  6:    if there is insufficient space or no rectangle of height r^k then  7:       a new shelf of appropriate height is created above the top-most shelf  8:       shelf++  9:    end if 10:    if rectangle Li is the first on the shelf then 11:       h(shelf) = r^k; H += h(shelf) 12:    end if 13: end while 14: print H and entire packing<\/pre>\n<\/div>\n<\/div>\n<h2>Azar<sub>Y<\/sub><\/h2>\n<p><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/88a\/700\/04f\/88a70004f8f042bd1de071dc92a46b7a.png\" align=\"right\"\/><br \/>  \u0414\u043b\u044f \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0438 \u0432\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043d\u0435\u043a\u043e\u0435 \u043f\u043e\u0440\u043e\u0433\u043e\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 0 &lt; <i>Y<\/i> &lt; 1\/2. \u0428\u0438\u0440\u0438\u043d\u0430 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432 \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0438 \u0441 \u0448\u0438\u0440\u0438\u043d\u043e\u0439 \u043f\u043e\u043b\u043e\u0441\u044b, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u0437\u0430 \u0435\u0434\u0438\u043d\u0438\u0446\u0443. \u041f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0438 \u0432\u044b\u0441\u043e\u0442\u043e\u0439 2<sup><i>j<\/i>-1<\/sup> &lt; h(L<sub>i<\/sub>) \u2264 2<sup><i>j<\/i><\/sup> \u0438 \u0448\u0438\u0440\u0438\u043d\u043e\u0439 2<sup>&#8212;<i>x<\/i>-1<\/sup> &lt; h(L<sub>i<\/sub>) \u2264 2<sup><i>-x<\/i><\/sup> \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043d\u0430 \u043e\u0434\u0438\u043d \u0443\u0440\u043e\u0432\u0435\u043d\u044c. \u0422\u043e \u0435\u0441\u0442\u044c \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u043f\u0430\u0440\u043e\u0439 (<i>x<\/i>, <i>j<\/i>) \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0446\u0435\u043b\u043e\u0433\u043e <i>j<\/i> \u0438 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e <i>x<\/i>.<\/p>\n<p>  \u041f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0438 \u0448\u0438\u0440\u0438\u043d\u043e\u0439 \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 <i>Y<\/i> \u043d\u0430\u0440\u0435\u043a\u0430\u044e\u0442\u0441\u044f <i>\u0431\u0443\u0444\u0435\u0440\u043d\u044b\u043c\u0438<\/i> \u0438 \u043f\u0430\u043a\u0443\u044e\u0442\u0441\u044f \u043a\u0430\u0436\u0434\u044b\u0439 \u043d\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c. \u0422\u043e \u0435\u0441\u0442\u044c \u0435\u0441\u043b\u0438 \u043f\u043e\u043f\u0430\u043b\u0441\u044f \u0442\u0430\u043a\u043e\u0439 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a, \u043d\u0443\u0436\u043d\u043e \u0441\u0440\u043e\u0447\u043d\u043e \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c, \u0432\u044b\u0441\u043e\u0442\u043e\u0439 \u0440\u0430\u0432\u043d\u044b\u0439 \u0435\u043c\u0443. \u0412\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 (\u043d\u0435-\u0431\u0443\u0444\u0435\u0440\u043d\u044b\u0435) \u043f\u0430\u043a\u0443\u044e\u0442\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c. \u041f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0439 \u2014 \u0432 \u0441\u043c\u044b\u0441\u043b\u0435 \u0441 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u043f\u0430\u0440\u043e\u0439 (<i>x<\/i>, <i>j<\/i>). \u0415\u0441\u043b\u0438 \u0432\u0434\u0440\u0443\u0433 \u043c\u0435\u0441\u0442\u0430 \u043d\u0435 \u0445\u0432\u0430\u0442\u0438\u043b\u043e, \u043d\u0435-\u0431\u0443\u0444\u0435\u0440\u043d\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u043c\u043e\u0436\u0435\u0442 \u0441\u0442\u0430\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u043c \u0432 \u043d\u043e\u0432\u043e\u043c \u0443\u0440\u043e\u0432\u043d\u0435, \u0442\u043e\u0433\u0434\u0430 \u0432\u044b\u0441\u043e\u0442\u0430 \u044d\u0442\u043e\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f \u0431\u0443\u0434\u0435\u0442 2<sup><i>j<\/i><\/sup>.<br \/>  \u041a\u0430\u043a\u0430\u044f-\u0442\u043e \u043d\u0435\u0437\u0434\u043e\u0440\u043e\u0432\u0430\u044f \u0438\u0435\u0440\u0430\u0440\u0445\u0438\u044f, \u0432 \u043e\u0431\u0449\u0435\u043c.<br \/>  \u0412 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 <i>Y<\/i>=0,4.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Azar<\/b><\/p>\n<div class=\"spoiler_text\"><b>Azar<sub>Y<\/sub><\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)}        the parameter Y and the strip width W. Output: The height H and the entire packing.  1: h(level) = 0; w(level) = 0; level = 0  2: while there is an unpacked rectangle do  3:    if w(Li) \u2265 Y then  4:       level++; w(level) = w(Li); h(level) = h(Li); H += h(level)  5:    else [w(Li) &lt; Y ]  6:       compute x and j such that           2^(j-1) &lt; h(Li) \u2264 2^j and 2^(-x-1) &lt; w(Li) \u2264 2^(-x)  7:       search for the lowest (x, j) level  8:       if no (x, j) level is available or Li is blocked then  9:          level++; h(level) = 2^j; H += h(level) 10:          w(level) += w(Li) 11:       else [(x, j) level is available and not blocked] 12:          w(level) += w(Li) 13:       end if 14:    end if 15: end while 16: print H and entire packing<\/pre>\n<\/div>\n<\/div>\n<h2>Compression algorithms<\/h2>\n<p><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/c76\/ff4\/075\/c76ff4075ccef48aba2ade4ec61d693c.png\" align=\"right\"\/><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/fc6\/3cc\/65f\/fc63cc65fcb29dc09cd722632ce48f8f.png\" align=\"right\"\/><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/407\/301\/0c1\/4073010c1bb036dc936a669d155e9b82.png\" align=\"right\"\/><br \/>  \u041a\u043e\u043c\u043f\u0440\u0435\u0441\u0441\u0438\u043e\u043d\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 BiNFL \u0438 \u043f\u043e \u0441\u0443\u0442\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0431\u043e\u0439 \u043f\u0430\u0442\u0447\u0438 \u043a \u043c\u0435\u0442\u043e\u0434\u0443 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438 \u0432\u0435\u0440\u0445\u043d\u0435\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f.<br \/>  \u041e\u0431\u0449\u0435\u0435 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u2014 \u0432\u0435\u0440\u0445\u043d\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0432\u0441\u0435\u0433\u0434\u0430 \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e.<br \/>  Compression Part Fit: \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430, \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u043d\u0430 \u0432\u0435\u0440\u0445\u043d\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c, \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442\u0441\u044f, \u0435\u0441\u0442\u044c \u043b\u0438 \u043f\u043e\u0434 \u043d\u0438\u043c \u043c\u0435\u0441\u0442\u043e \u043d\u0430 \u043d\u0438\u0436\u043d\u0435\u043c \u0443\u0440\u043e\u0432\u043d\u0435. \u0415\u0441\u043b\u0438 \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0432\u0438\u043d\u0443\u0442\u044c \u0435\u0433\u043e \u043d\u0430 \u043d\u0438\u0436\u043d\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0442\u0430\u043a, \u0447\u0442\u043e \u0447\u0430\u0441\u0442\u044c \u0435\u0433\u043e \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u043d\u0430 \u0432\u0435\u0440\u0445\u043d\u0435\u043c, \u043e\u043d \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u0442\u0441\u044f (\u043e\u0442\u0441\u044e\u0434\u0430 Part Fit \u2014 \u043e\u043d \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u043e \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u00ab\u0432\u0436\u0430\u0442\u00bb \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c). \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0441\u043d\u0438\u0437\u0438\u0442\u044c \u043e\u0431\u0449\u0443\u044e \u0432\u044b\u0441\u043e\u0442\u0443 \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f. \u0411\u043e\u043b\u044c\u0448\u0435 \u043d\u0430 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0443 \u043e\u043d \u043d\u0438\u043a\u0430\u043a \u043a\u0430\u0440\u0434\u0438\u043d\u0430\u043b\u044c\u043d\u043e \u043d\u0435 \u0432\u043b\u0438\u044f\u0435\u0442. \u041d\u0430 \u043f\u0435\u0440\u0432\u043e\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u0432\u0438\u0434\u043d\u043e \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a, \u0432\u0438\u0441\u044f\u0449\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u0443\u0440\u043e\u0432\u043d\u0435\u0439 \u2014 \u043e\u043d \u0438 \u0431\u044b\u043b \u0441\u0434\u0432\u0438\u043d\u0443\u0442.<br \/>  Compression Full Fit: \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430, \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u043d\u0430 \u0432\u0435\u0440\u0445\u043d\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c, \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442\u0441\u044f, \u043c\u043e\u0436\u0435\u0442 \u043b\u0438 \u043e\u043d \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0441\u043c\u0435\u0441\u0442\u0438\u0442\u044c\u0441\u044f \u0432\u043d\u0438\u0437 \u043d\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c. \u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0435\u0441\u043b\u0438 \u043c\u043e\u0436\u0435\u0442, \u0442\u043e \u0438 \u0441\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f. \u042d\u0442\u043e \u0434\u0430\u0435\u0442 \u043d\u0430\u043c \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432\u043e: \u043e\u0441\u0432\u043e\u0431\u043e\u0434\u0438\u0432\u0448\u0435\u0435\u0441\u044f \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u0435\u0441\u0442\u043e \u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u043e \u0434\u043b\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430. \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0438\u0441\u0443\u043d\u043e\u043a \u043d\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0442\u0430\u043a\u0443\u044e \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e, \u043d\u043e \u0437\u0430\u0442\u043e \u043d\u0430 \u043d\u0435\u043c \u043c\u043e\u0436\u043d\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u0434\u0432\u043e\u0438\u0445 \u043f\u0440\u043e\u0432\u0430\u043b\u0438\u0432\u0448\u0438\u0445\u0441\u044f.<br \/>  Compression Combo: \u0414\u0430-\u0434\u0430, \u044d\u0442\u043e \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u044f \u0434\u0432\u0443\u0445 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u0438, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u044f \u0438\u0445 \u043f\u043b\u044e\u0441\u043e\u0432. \u0422\u0440\u0435\u0442\u0438\u0439 \u0440\u0438\u0441\u0443\u043d\u043e\u043a \u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0438\u0440\u0443\u0435\u0442.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b CPF, CFF, CC<\/b><\/p>\n<div class=\"spoiler_text\"><b>Compression<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W. Output: The height H and the entire packing.  1: i = 0; H = 0  2: open new bi-level  3: packing on lower level is similar to BiNFL; H += h(lowerlevel)  4: if there is insufficient space to pack a rectangle on the lower level then  5:    call 'pack on the upper level'  6: end if  7: print H and entire packing Procedure 'pack on the upper level'  1: while there is an unpacked rectangle do  2:    if i \u2265 3 and Li is the first rectangle packed then  3:       justify according to the shorter           of the left-most and right-most rectangles  4:       slide rectangle downwards if there is sufficient space           and go to 12  5:    else  6:       if i \u2265 3 and Li is the second rectangle packed then  7:          right justify and go to 12  8:       else [rectangle does not fit]  9:          H += h(upperlevel); open new bi-level 10:       end if 11:    end if 12: end while<\/pre>\n<p>  <b>Compression Part Fit<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W. Output: The height H and the entire packing.  1: i = 0; H = 0  2: open a new bi-level  3: packing on lower level is similar to BiNFL; H += h(lowerlevel)  4: if there is insufficient space to pack a rectangle on the lower level then  5:    call 'pack on the upper level'  6: end if  7: print H and entire packing Procedure 'pack on the upper level'  1: while there is an unpacked rectangle do  2:    if h(Li) &gt; VerticalSpace and w(Li) \u2264 HorizontalSpace then  3:       shift rectangle Li downwards; go to 11  4:    else  5:       if h(Li) \u2264 VerticalSpace and W - w(level) \u2265 w(Li) then  6:          left justify; go to 11  7:       else [rectangle does not fit]  8:          H += h(upperlevel); open a new bi-level  9:       end if 10:    end if 11: end while<\/pre>\n<p>  <b>Compression Full Fit<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W. Output: The height H and the entire packing.  1: i = 0; H = 0  2: open a new bi-level  3: packing on lower level is similar to BiNFL; H += h(lowerlevel)  4: if there is insufficient space to pack a rectangle on the lower level then  5:    call 'pack on the upper level'  6: end if  7: print H and entire packing Procedure 'pack on the upper level'  1: while there is an unpacked rectangle do  2:    if h(Li) \u2264 VerticalSpace and w(Li) \u2264 HorizontalSpace then  3:       slide rectangle Li downwards; go to 11  4:    else  5:       if h(Li) \u2264 VerticalSpace and W - w(level) \u2265 w(Li) then  6:          left justify; go to 11  7:       else [rectangle does not fit]  8:          H += h(upperlevel); open new bi-level  9:       end if 10:    end if 11: end while<\/pre>\n<p>  <b>Compression Combo<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W. Output: The height H and the entire packing.  1: i = 0; H = 0  2: open a new bi-level  3: packing on lower level is similar to BiNFL; H += h(lowerlevel)  4: if there is insufficient space to pack a rectangle on the lower level then  5:    call 'pack on the upper level'  6: end if  7: print H and entire packing Procedure 'pack on the upper level'  1: while there is an unpacked rectangle do  2:    if w(Li) \u2264 HorizontalSpace then  3:       slide rectangle Li downwards; go to 11  4:    else  5:       if w(Li) &gt; HorizontalSpace and W - w(level) \u2265 w(Li) then  6:          left justify, go to 11  7:       else [rectangle does not fit]  8:          H += h(upperlevel); open new bi-level  9:       end if 10:    end if 11: end while<\/pre>\n<\/div>\n<\/div>\n<h2>Online fit<\/h2>\n<p><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/f5a\/3fd\/305\/f5a3fd305bf2d576e01e5df1a9235c4f.png\" align=\"right\"\/><br \/>  \u0411\u043e\u043b\u0435\u0435 \u0442\u0440\u0443\u0434\u043e\u0435\u043c\u043a\u0438\u0439 \u043c\u0435\u0442\u043e\u0434, \u0447\u0435\u043c \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0435, \u043d\u043e \u0438 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439. \u041e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 Burke \u0434\u043b\u044f <a href=\"http:\/\/habrahabr.ru\/post\/136225\/\">\u043e\u0444\u0444\u043b\u0430\u0439\u043d<\/a>-\u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u0437\u0430\u0434\u0430\u0447\u0438. \u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u0441\u043f\u0435\u043a\u0442\u044b \u044f, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u043d\u0430\u0440\u0438\u0441\u0443\u044e.<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/e68\/610\/8c1\/e686108c1272cd63e1f43b4717dffdb5.jpg\" align=\"left\"\/><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/571\/206\/9c1\/5712069c1883e4ff0c1657caf087ceb6.jpg\" align=\"left\"\/><\/p>\n<p>  \u0412 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u043e\u0431\u0440\u0430\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u043f\u0443\u0441\u0442\u044b\u0435 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 (Empty Areas), \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0431\u0443\u0434\u0435\u0442 \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0437\u0430\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c. \u041a\u0430\u043a \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f, \u0432\u0438\u0434\u043d\u043e \u043d\u0430 \u0444\u043e\u0442\u043e \u0441\u043b\u0435\u0432\u0430. \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0443\u0436\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043d\u0435\u043a\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043f\u043e\u043b\u043e\u0441\u044b.<br \/>  \u041f\u043e\u0441\u043b\u0435 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0438\u0437 \u043f\u0443\u0441\u0442\u043e\u0439 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c\u0441\u044f \u0434\u0432\u0435 (\u0430 \u043c\u043e\u0436\u0435\u0442 \u0438 \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c\u0441\u044f, you know).<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/7dc\/8f1\/c28\/7dc8f1c286a0f19999971da7ba8f348b.jpg\" align=\"left\"\/><img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/2cb\/eb0\/ea4\/2cbeb0ea43fdd3673ba4e59663f10c84.jpg\" align=\"left\"\/>\u0422\u0430\u043a\u0436\u0435 \u043e\u0434\u043d\u0438\u043c \u0448\u0430\u0433\u043e\u043c \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0441\u043e\u0437\u0434\u0430\u043d\u044b \u0441\u0440\u0430\u0437\u0443 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439 \u2014 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u043f\u043e\u0434 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u043c \u0430\u043d\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u043e \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u0438 \u0438 \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043f\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u00ab\u0441\u0442\u0443\u043f\u0435\u043d\u0435\u043a\u00bb. \u041d\u0430 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0444\u043e\u0442\u043e \u0435\u0449\u0435 \u0440\u0430\u0437 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043e \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u043f\u0443\u0441\u0442\u043e\u0439 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043d\u0430 \u0434\u0432\u0435 \u043f\u043e\u0441\u043b\u0435 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438 \u0442\u0443\u0434\u0430 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430 (\u043a\u0441\u0442\u0430\u0442\u0438, \u043c\u043d\u0435 \u043a\u0430\u0436\u0435\u0442\u0441\u044f, \u0432 \u044d\u0442\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u0435\u0435 \u0431\u044b\u043b\u043e \u0431\u044b \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0435\u0435 <i>\u043f\u043e \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u0438<\/i>).<br \/>  \u0412 \u043e\u0431\u0449\u0435\u043c, \u0447\u0435\u043c \u0434\u0430\u043b\u044c\u0448\u0435 \u0432 \u043b\u0435\u0441, \u0442\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0443\u0441\u0442\u043e\u0442. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u043f\u0440\u0438\u0441\u0442\u0430\u043b\u044c\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u0442\u0440\u0435\u043c\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0435\u043b\u044c\u0447\u0430\u044e\u0449\u0438\u0435 \u043f\u0443\u0441\u0442\u043e\u0442\u044b. \u0417\u0434\u0435\u0441\u044c \u043c\u043d\u0435 \u0432\u0438\u0434\u0438\u0442\u0441\u044f \u0435\u0449\u0435 \u043e\u0434\u043d\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f: \u043c\u043e\u0436\u043d\u043e \u0432\u0432\u0435\u0441\u0442\u0438 \u043c\u0435\u0440\u0443 \u0446\u0435\u043b\u0435\u0441\u043e\u043e\u0431\u0440\u0430\u0437\u043d\u043e\u0439 \u043f\u043b\u043e\u0449\u0430\u0434\u0438 \u0438 \u043e\u0442\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0442\u044c \u043d\u0435\u0443\u0433\u043e\u0434\u043d\u044b\u0435.<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/8aa\/4ff\/087\/8aa4ff08741e3411e04f1bda24fa7630.jpg\" align=\"right\"\/>\u0415\u0441\u043b\u0438 \u043d\u0438 \u043e\u0434\u043d\u0430 \u043f\u0443\u0441\u0442\u0430\u044f \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u043d\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442, \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0430 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u0442\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c Burke. \u042f \u043d\u0430\u043f\u043e\u043c\u043d\u044e. \u0421\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u043a\u0430\u0440\u0442\u0430 \u0432\u044b\u0441\u043e\u0442 \u0434\u043b\u044f \u043f\u043e\u043b\u043e\u0441\u044b, \u0438 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u043f\u0440\u0438\u043c\u0435\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u0441\u0430\u043c\u0443\u044e \u043d\u0438\u0437\u043a\u0443\u044e \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u043e\u0431\u043b\u0430\u0441\u0442\u044c. \u0415\u0441\u043b\u0438 \u043e\u043d \u0442\u0443\u0434\u0430 \u043d\u0435 \u0432\u0445\u043e\u0434\u0438\u0442, \u043d\u0438\u0437\u043a\u043e\u0435 \u043c\u0435\u0441\u0442\u043e \u00ab\u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f\u00bb \u0434\u043e \u0443\u0440\u043e\u0432\u043d\u044f \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0439 \u0441\u0442\u0443\u043f\u0435\u043d\u044c\u043a\u0438, \u0438 \u043f\u043e\u0438\u0441\u043a \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u0442\u0441\u044f. \u0422\u0430\u043a \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u0442\u043e\u043b\u043a\u043d\u0443\u0442\u043e \u043d\u0430 \u0441\u0430\u043c\u044b\u0439 \u0432\u0435\u0440\u0445, \u0438 \u0442\u043e\u0433\u0434\u0430 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0435\u0449\u0435 \u043e\u0434\u0438\u043d \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0443\u0441\u0442\u043e\u0433\u043e \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 (\u0441\u043c. \u0441\u043f\u0440\u0430\u0432\u0430).<br \/>  \u0422\u0430 \u0436\u0435 \u043a\u0430\u0440\u0442\u0430 \u0432\u044b\u0441\u043e\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u0434\u043b\u044f \u0432\u044b\u044f\u0432\u043b\u0435\u043d\u0438\u044f \u043f\u0443\u0441\u0442\u044b\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439.<\/p>\n<p>  \u0412 \u043e\u0431\u0449\u0435\u043c-\u0442\u043e, \u0432\u0441\u0435 \u0443\u0436\u0435 \u0441\u043a\u0430\u0437\u0430\u043d\u043e. \u0421\u043f\u0435\u0440\u0432\u0430 \u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u0442\u044c \u043f\u043e \u043f\u0443\u0441\u0442\u044b\u043c \u043e\u0431\u043b\u0430\u0441\u0442\u044f\u043c, \u0437\u0430\u0442\u0435\u043c \u0432 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043d\u0438\u0437\u043a\u043e\u0435 \u043c\u0435\u0441\u0442\u043e, \u0438 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u2014 \u0441\u0432\u0435\u0440\u0445\u0443, \u0432\u044b\u0440\u043e\u0436\u0434\u0435\u043d\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u00ab\u0441\u0430\u043c\u043e\u0433\u043e \u043d\u0438\u0437\u043a\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430\u00bb.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c OF<\/b><\/p>\n<div class=\"spoiler_text\"><b>Online Fit<\/b>  <\/p>\n<pre>Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W. Output: The height H and the entire packing.  1: i = 0; H = 0  2: Create a linear array whose number of elements are equal to W  3: while there is an unpacked rectangle do  4:    i++  5:    Search the list of empty areas for sufficient space to pack Li  6:    if w(EmptyArea) \u2265 w(Li) and h(EmptyArea) \u2265 h(Li) then  7:       pack rectangle in empty area  8:    else  9:       if rectangle does not fit in any of the empty areas then 10:          search the linear array for available packing width 11:       else [there is insufficient space in linear array] 12:          pack rectangle on top left justified              from the index leading to smaller space 13:       end if 14:    end if 15: end while 16: H = highest entry in the linear array 17: print H and entire packing<\/pre>\n<\/div>\n<\/div>\n<h2>\u041f\u043e\u0441\u043b\u0435\u0441\u043b\u043e\u0432\u0438\u0435<\/h2>\n<p>  \u0427\u0442\u043e\u0431\u044b \u0440\u0430\u0437\u0432\u0435\u044f\u0442\u044c \u043e\u0449\u0443\u0449\u0435\u043d\u0438\u0435 \u0431\u0435\u0441\u0446\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0449\u0435\u0433\u043e, \u043f\u0440\u0438\u0432\u0435\u0434\u0443 \u043e\u0434\u0438\u043d \u0438\u0437 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0445, \u043d\u043e \u0432\u0434\u043e\u0445\u043d\u043e\u0432\u043b\u044f\u044e\u0449\u0438\u0445 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u043e\u0439 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438 \u0432 \u043f\u043e\u043b\u0443\u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u0443\u044e \u043f\u043e\u043b\u043e\u0441\u0443. \u042d\u0442\u043e \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a \u0437\u0430\u0434\u0430\u0447 \u0434\u043b\u044f \u043c\u043d\u043e\u0433\u043e\u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u044b. \u0412 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u043c \u0441\u043e\u0444\u0442\u0435 \u0434\u043b\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u00ab\u0432\u0437\u0440\u043e\u0441\u043b\u044b\u0435\u00bb \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043d\u043e \u0441\u0430\u043c\u0430 <a href=\"http:\/\/en.wikipedia.org\/wiki\/Multiprocessor_scheduling\">\u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/a> \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a 2DSP. \u0412 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 \u0440\u0430\u0431\u043e\u0442\u044b \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 \u043f\u043e\u0442\u043e\u043a \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u044e\u0449\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u043d\u0435 \u0447\u0442\u043e \u0438\u043d\u043e\u0435, \u043a\u0430\u043a online \u0434\u0430\u043d\u043d\u044b\u0435 \u0434\u043b\u044f \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438: \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u043f\u043e \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u0438 \u2014 \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044f\u0434\u0435\u0440, \u043f\u043e \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u0438 \u2014 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0437\u0430\u0434\u0430\u0447\u0438. (\u0412\u0441\u0435 \u043a\u0430\u043a \u043d\u0430 \u0437\u0430\u0440\u0435 \u0442\u0435\u0445\u043d\u043e\u043b\u043e\u0433\u0438\u0439: \u0432\u0441\u0442\u0430\u0435\u0448\u044c \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043a \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u0443 \u0438 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043f\u0440\u0435\u0434\u0443\u043f\u0440\u0435\u0436\u0434\u0430\u0435\u0448\u044c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u0435\u0431\u0435 \u043d\u0443\u0436\u043d\u043e \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0432 \u0438 \u043a\u0430\u043a \u0434\u043e\u043b\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u043a\u0440\u0443\u0442\u0438\u0442\u044c\u0441\u044f \u0442\u0432\u043e\u044f \u043f\u0435\u0440\u0444\u043e\u043a\u0430\u0440\u0442\u0430). \u041f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a \u0434\u043e\u043b\u0436\u0435\u043d \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u044b \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043c\u043e\u043c\u0435\u043d\u0442 \u0437\u0430\u043f\u0443\u0441\u043a\u0430. \u0412 \u0447\u0438\u0441\u0442\u043e\u043c \u0432\u0438\u0434\u0435, \u043a\u0441\u0442\u0430\u0442\u0438, \u043d\u0438 \u043e\u0434\u0438\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u043b\u044c\u0437\u044f, \u0442\u0430\u043a \u043a\u0430\u043a \u0432\u0440\u0435\u043c\u044f \u043a\u0430\u043f\u0430\u0435\u0442, \u043f\u043e\u043a\u0430 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a \u0436\u0434\u0435\u0442 \u0437\u0430\u0434\u0430\u0447\u0443 \u0438\u043b\u0438 \u0434\u0443\u043c\u0430\u0435\u0442 \u043d\u0430\u0434 \u0435\u0435 \u0440\u0430\u0437\u043c\u0435\u0449\u0435\u043d\u0438\u0435\u043c. \u0414\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u0443 \u043c\u043e\u0433\u0443\u0442 \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0442\u044c \u0440\u0443\u043a\u0438 \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u044f: \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 \u0437\u0430\u0434\u0430\u0447; \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f; \u0445\u0430\u0440\u0434\u0432\u0430\u0440\u043d\u044b\u0435 \u0437\u0430\u0434\u0435\u0440\u0436\u043a\u0438 \u0438 \u0441\u0430\u043c\u043e\u043e\u0431\u0441\u043b\u0443\u0436\u0438\u0432\u0430\u043d\u0438\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b, \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u043f\u0435\u0440\u0435\u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0441 \u0443\u0447\u0435\u0442\u043e\u043c \u043e\u0442\u043a\u0430\u0437\u0430\u0432\u0448\u0438\u0445 \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0432; \u0441\u043e\u043f\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0430 \u043a\u043e\u043c\u043c\u0443\u043d\u0438\u043a\u0430\u0446\u0438\u0439 \u0432\u043d\u0443\u0442\u0440\u0438 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440\u043e\u0439 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430, etc.<br \/>  \u041b\u044e\u0431\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u0435\u043d \u0432 \u0441\u0432\u043e\u0435\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u0442\u0440\u043e\u0433\u043e\u0441\u0442\u0438, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043d\u0430\u0447\u043d\u0435\u0448\u044c \u043f\u0440\u0438\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u043a \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0439 \u0436\u0438\u0437\u043d\u0438.<\/p>\n<p>  \u0418 \u043d\u0430\u043f\u043e\u0441\u043b\u0435\u0434\u043e\u043a \u2014 \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0441\u0442\u0438\u043a\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0432 \u043f\u0440\u0438\u044f\u0442\u043d\u043e\u043c \u043e\u0431\u0435\u0437\u043b\u0438\u0447\u0435\u043d\u043d\u043e\u043c \u0432\u0438\u0434\u0435. \u0417\u0434\u0435\u0441\u044c \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0441\u043e\u0442\u044b \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438 (\u0441\u0443\u043c\u043c\u0430 \u043f\u043b\u043e\u0449\u0430\u0434\u0435\u0439 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432, \u0434\u0435\u043b\u0435\u043d\u043d\u0430\u044f \u043d\u0430 \u0448\u0438\u0440\u0438\u043d\u0443 \u043f\u043e\u043b\u043e\u0441\u044b) \u043a \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u043e\u0439.  <\/p>\n<table>\n<tr>\n<th>NFL<\/th>\n<th>FFL<\/th>\n<th>BFL<\/th>\n<th>BiNFL<\/th>\n<th>NFS<\/th>\n<th>FFS<\/th>\n<th>BFS<\/th>\n<th>HS<\/th>\n<th>Azar<sub>Y<\/sub><\/th>\n<th>CPF<\/th>\n<th>CFF<\/th>\n<th>CC<\/th>\n<th>OF<\/th>\n<\/tr>\n<tr>\n<td>0,56<\/td>\n<td>0,63<\/td>\n<td>0,75<\/td>\n<td>0,56<\/td>\n<td>0,45<\/td>\n<td>0,57<\/td>\n<td>0,57<\/td>\n<td>0,37<\/td>\n<td>0,44<\/td>\n<td>0,60<\/td>\n<td>0,59<\/td>\n<td>0,63<\/td>\n<td>0,72<\/td>\n<\/tr>\n<\/table>\n<hr\/>\n<p>  \u041a\u043e\u0434 (Qt):<br \/>  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b <a href=\"http:\/\/pastebin.com\/XtdEHAR6\">packager.h<\/a> <a href=\"http:\/\/pastebin.com\/eGXRZ65c\">packager.cpp<\/a><br \/>  \u0413\u0443\u0439 <a href=\"http:\/\/pastebin.com\/iqFU7Qg2\">window.h<\/a> <a href=\"http:\/\/pastebin.com\/qWk7q7EX\">window.cpp<\/a> <a href=\"http:\/\/pastebin.com\/4m2DW4S0\">renderarea.h<\/a> <a href=\"http:\/\/pastebin.com\/s0QkUeq5\">renderarea.cpp<\/a> <a href=\"http:\/\/pastebin.com\/LMpUBUEj\">main.cpp<\/a>    \t   \t<\/p>\n<div class=\"clear\"><\/div>\n<\/p><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"http:\/\/habrahabr.ru\/post\/160869\/\"> http:\/\/habrahabr.ru\/post\/160869\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div class=\"content html_format\">   \t<img decoding=\"async\" src=\"http:\/\/habrastorage.org\/storage2\/c94\/07d\/b77\/c9407db7753a73de4241c3f908049528.jpg\" align=\"right\"\/>\u042d\u0442\u043e \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0435\u043d\u0438\u0435 <a href=\"http:\/\/habrahabr.ru\/post\/136225\/\">\u043f\u043e\u0441\u0442\u0430<\/a> \u043f\u0440\u043e \u043e\u0444\u0444\u043b\u0430\u0439\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0438.<\/p>\n<p>  \u0421\u0443\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0438: \u0438\u043c\u0435\u0435\u043c \u043f\u043e\u043b\u0443\u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u0443\u044e \u043f\u043e\u043b\u043e\u0441\u0443 \u2014 \u043a\u0430\u043a \u0432 \u0442\u0435\u0442\u0440\u0438\u0441\u0435, \u0442\u043e\u043b\u044c\u043a\u043e \u0431\u0435\u0437 game over&#8217;\u0430, \u0438 \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432. \u0414\u0430\u043d\u043d\u044b\u0435 \u043e \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430\u0445 \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u044e\u0442 \u0432 \u0440\u0435\u0436\u0438\u043c\u0435 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438; \u043a\u0430\u0436\u0434\u044b\u0439 \u043d\u043e\u0432\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0435\u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0440\u0430\u0437\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0435 \u0434\u0432\u0438\u0433\u0430\u0442\u044c \u0441 \u043c\u0435\u0441\u0442\u0430. \u0426\u0435\u043b\u044c \u2014 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043e\u0431\u0449\u0443\u044e \u0432\u044b\u0441\u043e\u0442\u0443 \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432.<br \/>  \u042d\u0442\u043e online-\u0432\u0430\u0440\u0438\u0430\u0446\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u0431 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0435 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u043e\u0432 \u0432 \u043f\u043e\u043b\u0443\u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u0443\u044e \u043f\u043e\u043b\u043e\u0441\u0443 (2 Dimensional Strip Packing, 2DSP).<\/p>\n<p>  \u0427\u0443\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0441\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435, \u0430 \u043f\u043e\u043a\u0430, \u0431\u0435\u0437 \u043b\u0438\u0448\u043d\u0438\u0445 \u0441\u043b\u043e\u0432, \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c.  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-160869","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/160869","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=160869"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/160869\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=160869"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=160869"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=160869"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}