![]() ![]() Roughly speaking, RF packs items from left to right with their bottom along the line of height H0 until there is no more room. Remaining items are sorted in non-increasing height and will be packed above the height H0 reached by those greater than 1/2. RF first stacks all items of width greater than 1/2. RF also normalizes the width of the strip and the items so that the strip is of unit width. OPT(I)+(53/8)H, where H is the maximum height of the items the asymptotic bound of 5/4 is tight.Again if there is no space in these regions, the item is packed to R5 using NFDH. , R4 by the (generalized) NFDH algorithm.Finally, items of size at most 1/5 are packed to the spaces in R1, If there is no such space, the item is packed to Ri by BL. Since BL leaves a space of increasing width from top to bottom at the right side of the strip, UD takes this advantage by first packing the item to Rj for j = 1, Basically, some items of width in the range (1/i+1, 1/i], for 1 <= i <= 4, are packed to region Ri by BL. The strip is also divided into five regions R1, UD orders the items in non-increasing width and then divides the items into five groups, each with width in the range (1/2, 1], (1/3,1/2], (1/4,1/3], (1/5,1/4], (0,1/5]. The width of the strip and the items are normalized so that the strip is of unit width. UD uses a combination of BL and a generalization of NFDH. Note that BL is not a level-oriented packing algorithm. BL packs the next item as near to the bottom as it will fit and then as close to the left as it can go without overlapping with any packed item. If no level can accommodate R, a new level is created.īL first order items by non-increasing width. OPT(I)+1 the asymptotic bound of 2 is tight.īest-Fit Decreasing Height (BFDH) algorithmīFDH packs the next item R (in non-increasing height) on the level, among those that can accommodate R, for which the residual horizontal space is the minimum.Otherwise, the current level is "closed" and a new level is created.Īpproximation ratio: NFDH(I) <= 2 ![]() NFDH packs the next item R (in non-increasing height) on the current level if R fits. Next-Fit Decreasing Height (NFDH) algorithm
0 Comments
Leave a Reply. |