About two-dimensional packaging: offline algorithms
Today, dear Habr, I will tell you a story about combinatorial optimization.
Since ancient times (at least since the beginning of the last century) mathematicians wondered how to optimally place a certain amount ofbeer of necessary and useful items in a backpack. The knapsack problem and its subtasks were formulated - thousands of them! - who are interested computer scientists, cryptographers and even linguists.
The knapsack problem in containers ( Bin Packing Problem ), one of the varieties of which is two-dimensional packaging (2-Dimensional Bin Packing), spun off the knapsack problem. Rejecting several variations again, we will finally arrive at a two-dimensional package in a semi-unlimited strip (2-Dimensional Strip Packing, 2DSP). Do you feel how much interesting is already left behind the scenes? But we have not finished wading through the classification. 2DSP has two input data options: when the set of objects to be packaged is known in advance (offline problem) and when data arrives in chunks (online problem).
This article discusses the algorithms for solving offline-variant 2DSP. Under the cut a bit of hardware and a lot of pictures with colored squares.
')
As a special case of a two-dimensional packaging task, 2DSP consists in packing objects of a specific shape into a finite number of containers of a particular shape in such a way that the number of containers used is the smallest or the number or volume of objects (which are packaged) is greatest. The difference with two-dimensional packaging is that there is only one container, and instead of minimizing the number of containers, we minimize the height of one occupancy. Ensure maximum packing density if you want.
Since the problem is NP-hard, research has focused mainly on the development of approximate solution algorithms. (A genetic algorithm was mentioned on Habré). Approximate algorithms find the optimal solution with a certain accuracy, but do not guarantee optimal packaging for any data set. In this case, the optimality criterion depends on what you tried to optimize.
I will talk about the simplest strategies and how this all applies in life (except for a backpack with a beer).
So, we have a set of n rectangles and a semi-limited container-glass with a fixed width W and infinite height. Each rectangle in width does not exceed W. The task is to place the rectangles in a glass without overlaps and intersections so that the glass becomes as full as possible. Let's agree that all rectangles should be packed orthogonally, they cannot be rotated.
It can be seen that the problem has an ideal solution, in which the height of the packed rectangles is equal to their total area divided by the width of the strip.
For an offline version of 2DSP, the size of all packed rectangles is immediately known, so you can sort them, select them according to a certain criterion, group them, or just stick them in suitable places. Most of the algorithms are based on this:
Flat algorithms place rectangles strictly closely to each other, but this is not the most successful strategy, as it may seem at first glance. Level divide the strip into levels equal in height to one of the selected rectangles, and place all the others at a specific level according to a certain criterion. Shelfs predetermine several shelves (shelves) at once, and stuff rectangles through them, this behavior is typical of online-algorithms, and this is a completely different story.
Than spread to common words, better about everything in order.
The algorithm, as they say, "in the forehead." The rectangles are sorted by non-increasing height (Decreasing High hints), the highest is located in the lower left corner of the strip, thereby initializing the first level, equal in height to it. The remaining rectangles are arranged from left to right, as long as there is space at the current level. A rectangle that does not fit in the level is placed on top, forming the next level, and so on.
The illustrations for each algorithm will be made for the following two examples: for clarity, the shape of the left rectangles to the elongated, in the right - more square.
NFDH Algorithm
Similar to the previous algorithm, with the difference that for each next rectangle a place is searched not only at the last level, but starting from the lowest one. From here and "first fit" - the rectangle is located on the first suitable level from below. Intuitively, the packaging will be better. Another significant difference is in performance, since in the worst case it is necessary to consider all levels from bottom to top at every step.
FFDH algorithm
Modification of the previous algorithm. Its essence is that of the levels that are suitable for packing the next rectangle, not the first, but the best one is chosen. The best level is one on which there will be a minimum of space after packing the current rectangle. Simply put, the minimum suitable space is chosen, which contributes to a better level filling.
BFDH Algorithm
It is worth staying in more detail. Knapsack 0-1 is a special case of the knapsack problem; it is remarkable that in addition to answering the main question (no, not 42, but the resulting volume of packaging) also provides a solution - a list of items that need to be packed. The procedure is as follows: the rectangles are sorted by non-increasing height; the first rectangle is packed to a new level; for this level, the solution of the Knapsack 0-1 problem is found, which gives us a list of rectangles maximized over the area. The selected rectangles are packed and retrieved from the unpacked list, the level is closed and a new one is opened - initialized, as usual, by the first (highest) of the remaining ones. Repeat until there are rectangles.
Algorithm KP01
Algorithm designed to improve the FFDN on the divide-and-conquer principle. For a start, rectangles are selected that are wider than half a strip. They will be packed first. Even wider ones are selected from them - wider than 2/3 of the band; they are packaged by the FFDH algorithm. Above them, starting from the next level (let's call it level R), the remaining ones are packed, those that are still wider than 1/2, but already 2/3. They are also packaged with FFDH. This division creates a free region 1/3 wide to the right of the newly packed, starting at level R and ending with the current upper bound of the package (that is, it does not extend beyond the rectangles 1/2 <width <= 2/3). All remaining rectangles, which are narrower than 1/2 of the strip, are packed using the same FFDH first of all into the resulting region, and if they are not placed, they are placed on top. In words it sounds cumbersome, the picture should be clearer. And for those who are already tired of my literary exercises - pseudocode:
SF Algorithm
Apparently, this algorithm was sharpened by a certain nature of the input data, well, any practical situation has the right to exist. Now you will understand everything yourself. Sorted, as usual, by non-increasing height, the rectangles are combined into pairs so that the difference in height in the pair does not exceed the specified proportion, usually 0-10%. Another condition is that their total width fit into the strip. The resulting "super-rectangles" are packed together with the remaining ones without a pair using NFDH and FFDH, the best solution is chosen.
There is a variation of this algorithm, when the rectangles are sorted by width and vertically combined, with the same condition of maximum deviation of width in a pair by a specified number of percent.
Algorithm Join
If you are still perplexed about the remaining space, then this algorithm is for you. The rectangles are sorted by non-increasing height (unexpected, yes?) And the BFDH algorithm is applied with some modifications. Each level has a "floor" (floor) and "ceiling" (ceiling). As long as possible, the rectangles are packed on the "floor" from left to right. When the place ends, an attempt is made to pack to the "ceiling" from right to left; if there is no space on the ceiling, then only a new level begins. In the best traditions of BFDH, at every step all levels are viewed - first the “floor”, then the “ceiling” - for the presence of the most suitable place. Packaging, as you can see, is not bad. The method successfully packs the smallest rectangles along the “ceilings”.
FCNR algorithm
It is time for "flat" algorithms, without division into levels. The Sleator algorithm uses the intuitive principle of packing a backpack: fold the largest items to the bottom and fill them up with small ones. Here's what it looks like. The widest are chosen from the rectangles, half of the strip is wider, as you have already guessed, and chaotically fit each other with alignment on the left edge. The rest are sorted by non-ascending height and begin to stack one after the other, from left to right, from the top to the already laid ones. As soon as their total width exceeds half the width of the strip, the rest are spread over each other, either to the left (starting from the left edge of the strip), then to the right (from the middle), according to the principle “where it is less at the moment”. As can be seen from the figures, this method makes it easier to stack books than boxes.
Algorithm Sleator
Again, the smooth algorithm for which an additional “height map” is introduced:
This is an array by which the least populated areas and their width can be tracked as the band fills up. At the beginning it is filled with zeros. The rectangles are sorted by non-increasing, suddenly, widths. Then, at each step of the algorithm:
1. Calculates the position of the lowest area - the index of the minimum value of the array;
2. The most suitable rectangle is selected - firstly, which fits in this area, secondly, as much as possible filling it in width;
3. If a suitable rectangle is found, it is placed in this area in one of the ways:
3.1 On the left edge of the area;
3.2 Closer to a higher neighbor, if one of the neighbors is the edge of a strip, then closer to the edge;
3.3 Closer to a lower neighbor, if one of the neighbors is the edge of the strip, then farther from the edge. To the array values ​​corresponding to the width of the rectangle, its height is added.
4. If there is no suitable rectangle, the area is “filled” by aligning its height to the height of the nearest edge.
Did you already want to write a Tetris bot using this algorithm?
Burke algorithm
The result of each algorithm is the level of fullness of the band; the smaller, the better. It can be estimated by the optimal attitude towards it:
Let's compare the obtained results for the two given sets of source data:
We see that Floor Ceiling won for both data sets. It may be noted that Sleator showed a much better result for the first set, and Join, on the contrary, is more suitable for the second. But all this is nothing more than statistics.
Due to its simple formulation, the task of binary packaging can be pulled to a huge number of practical applications: directly to the packaging of objects or the cutting of material, the distribution of funds, the planning of tasks on clusters, etc. There are few refined tasks in life, but, having limited some conditions, it is possible to reduce the situation to a beautiful mathematical model having a good solution that can be achieved in polynomial time. And once, as a result of the butterfly effect, the discarded conditions will weigh heavily and the decision will fly to all the Nameless. Because of such assumptions, the world is imperfect.
Something I was distracted. In the next part, I hope to talk about the online version of the problem and the shelf algorithms. Good luck!
Sources of inspiration:
Nthabiseng Ntene An Algorithmic Approach to the 2D Oriented Strip Packing Problem
David Pisinger Knapsack problem
Survey on two-dimensional packing
Level Algorithms and Shelf Algorithms (careful, design-tear out eyes)
Code (Qt):
Algorithms packager.h packager.cpp
Gui window.h window.cpp renderarea.h renderarea.cpp main.cpp
UPD: Online algorithms
Since ancient times (at least since the beginning of the last century) mathematicians wondered how to optimally place a certain amount of
The knapsack problem in containers ( Bin Packing Problem ), one of the varieties of which is two-dimensional packaging (2-Dimensional Bin Packing), spun off the knapsack problem. Rejecting several variations again, we will finally arrive at a two-dimensional package in a semi-unlimited strip (2-Dimensional Strip Packing, 2DSP). Do you feel how much interesting is already left behind the scenes? But we have not finished wading through the classification. 2DSP has two input data options: when the set of objects to be packaged is known in advance (offline problem) and when data arrives in chunks (online problem).
This article discusses the algorithms for solving offline-variant 2DSP. Under the cut a bit of hardware and a lot of pictures with colored squares.
')
What is the problem?
As a special case of a two-dimensional packaging task, 2DSP consists in packing objects of a specific shape into a finite number of containers of a particular shape in such a way that the number of containers used is the smallest or the number or volume of objects (which are packaged) is greatest. The difference with two-dimensional packaging is that there is only one container, and instead of minimizing the number of containers, we minimize the height of one occupancy. Ensure maximum packing density if you want.
Since the problem is NP-hard, research has focused mainly on the development of approximate solution algorithms. (A genetic algorithm was mentioned on Habré). Approximate algorithms find the optimal solution with a certain accuracy, but do not guarantee optimal packaging for any data set. In this case, the optimality criterion depends on what you tried to optimize.
I will talk about the simplest strategies and how this all applies in life (except for a backpack with a beer).
So, we have a set of n rectangles and a semi-limited container-glass with a fixed width W and infinite height. Each rectangle in width does not exceed W. The task is to place the rectangles in a glass without overlaps and intersections so that the glass becomes as full as possible. Let's agree that all rectangles should be packed orthogonally, they cannot be rotated.
 |  |  |  |
| Initial data (early 20th century, cubism) | Semi-limited strip | Packing Option (Worse) | Packing option (better) |
It can be seen that the problem has an ideal solution, in which the height of the packed rectangles is equal to their total area divided by the width of the strip.
Zoo Algorithm
For an offline version of 2DSP, the size of all packed rectangles is immediately known, so you can sort them, select them according to a certain criterion, group them, or just stick them in suitable places. Most of the algorithms are based on this:
- level (level)
- shelf (shelf)
- flat
Flat algorithms place rectangles strictly closely to each other, but this is not the most successful strategy, as it may seem at first glance. Level divide the strip into levels equal in height to one of the selected rectangles, and place all the others at a specific level according to a certain criterion. Shelfs predetermine several shelves (shelves) at once, and stuff rectangles through them, this behavior is typical of online-algorithms, and this is a completely different story.
Than spread to common words, better about everything in order.
Next Fit Decreasing High
The algorithm, as they say, "in the forehead." The rectangles are sorted by non-increasing height (Decreasing High hints), the highest is located in the lower left corner of the strip, thereby initializing the first level, equal in height to it. The remaining rectangles are arranged from left to right, as long as there is space at the current level. A rectangle that does not fit in the level is placed on top, forming the next level, and so on.
The illustrations for each algorithm will be made for the following two examples: for clarity, the shape of the left rectangles to the elongated, in the right - more square.
NFDH Algorithm
Input: The number of rectangles to be packed n,
the dimensions of the rectangles
{w (Li); h (Li)} and the strip width W.
Output:
1: level = 0; h (level) = 0; w (level) = 0; i = 1
2: Sort the rectangles in order of non-increasing height such that h (L1) ≥ h (L2) ≥ ... ≥ h (Ln)
3: Pack rectangle Li left-justifed at the bottom of the strip
4: h (level) = h (Li); w (level) = w (Li)
5: for i = 2..n do
6: if W - w (level) ≥ w (Li) then
7: pack rectangle Li-1
8: w (level) + = w (Li)
9: else [W - w (level) <w (Li)]
10: create a new level
11: level ++; w (level) = w (Li); h (level) = h (level-1) + h (Li)
12: end if
13: end for
14: print H = h (level) First Fit Decreasing High
Similar to the previous algorithm, with the difference that for each next rectangle a place is searched not only at the last level, but starting from the lowest one. From here and "first fit" - the rectangle is located on the first suitable level from below. Intuitively, the packaging will be better. Another significant difference is in performance, since in the worst case it is necessary to consider all levels from bottom to top at every step.
FFDH algorithm
Input: The number of rectangles to be packed n,
the dimensions of the rectangles
{w (Li); h (Li)} and the strip width W.
Output:
1: level = 0; h (level) = 0; i = 1; LevelNum = 1
2: Sort the rectangles in order of non-increasing height such that h (L1) ≥ h (L2) ≥ ... ≥ h (Ln)
3: Pack rectangle Li left-justifed at the bottom of the strip; h (level + 1) = h (Li)
4: for i = 2..n do
5: Search all levels with lowest space
6: if such a level exist then
7: pack rectangle Li left justified on that level
8: else [there is a space in all existing levels]
9: LevelNum ++; level = LevelNum; h (level) = h (level-1) + h (Li)
10: pack rectangle Li on the new level
11: end if
12: end for
13: print H = h (level) Best Fit Decreasing High
Modification of the previous algorithm. Its essence is that of the levels that are suitable for packing the next rectangle, not the first, but the best one is chosen. The best level is one on which there will be a minimum of space after packing the current rectangle. Simply put, the minimum suitable space is chosen, which contributes to a better level filling.
BFDH Algorithm
Input: The number of rectangles to be packed n,
the dimensions of the rectangles
{w (Li); h (Li)} and the strip width W.
Output:
1: level = 0; h (level) = 0; i = 1; LevelNum = 1
2: Sort the rectangles in order of non-increasing height such that h (L1) ≥ h (L2) ≥ ... ≥ h (Ln)
3: Pack rectangle Li left-justifed at the bottom of the strip; h (level + 1) = h (Li)
4: for i = 2..n do
5: search residual space
6: if such a level exist then
7: pack rectangle Li left justified on that level
8: else [there is a space in all existing levels]
9: create a new level
10: LevelNum ++; level = LevelNum; h (level) = h (level-1) + h (Li)
11: end if
12: end for
13: print H = h (level) Knapsack 0-1
It is worth staying in more detail. Knapsack 0-1 is a special case of the knapsack problem; it is remarkable that in addition to answering the main question (no, not 42, but the resulting volume of packaging) also provides a solution - a list of items that need to be packed. The procedure is as follows: the rectangles are sorted by non-increasing height; the first rectangle is packed to a new level; for this level, the solution of the Knapsack 0-1 problem is found, which gives us a list of rectangles maximized over the area. The selected rectangles are packed and retrieved from the unpacked list, the level is closed and a new one is opened - initialized, as usual, by the first (highest) of the remaining ones. Repeat until there are rectangles.
Algorithm KP01
Input: The number of rectangles to be packed n,
the dimensions of the rectangles
{w (Li); h (Li)} and the strip width W.
Output:
1: Sort the rectangles in order of non-increasing height such that h (L1) ≥ h (L2) ≥ ... ≥ h (Ln)
2: level = 0
3: while there are unpacked rectangles do
4: pack first unpacked rectangle, Li say
5: h (level) + = h (Li)
6: solve KP01 instance
7: pack selected rectangles
8: level = level + 1
9: end while
10: print H = h (level) Split fit
Algorithm designed to improve the FFDN on the divide-and-conquer principle. For a start, rectangles are selected that are wider than half a strip. They will be packed first. Even wider ones are selected from them - wider than 2/3 of the band; they are packaged by the FFDH algorithm. Above them, starting from the next level (let's call it level R), the remaining ones are packed, those that are still wider than 1/2, but already 2/3. They are also packaged with FFDH. This division creates a free region 1/3 wide to the right of the newly packed, starting at level R and ending with the current upper bound of the package (that is, it does not extend beyond the rectangles 1/2 <width <= 2/3). All remaining rectangles, which are narrower than 1/2 of the strip, are packed using the same FFDH first of all into the resulting region, and if they are not placed, they are placed on top. In words it sounds cumbersome, the picture should be clearer. And for those who are already tired of my literary exercises - pseudocode:
SF Algorithm
Input: The number of rectangles to be packed n,
the dimensions of the rectangles
{w (Li); h (Li)} and the strip width W.
Output:
1: Let m ≥ 1 for all rectangles in L
have width at most 1 = m
2: Partition the list of rectangles L into two sublists of L1 and L2
such that L1 is a list of rectangles of width greater than
1 / (m + 1), while L2 is a list of rectangles of width at most 1 / (m + 1)
3: Pack the L1 rectangles into the strip, using the FFDH algorithm
4: Rearrange the blocks of packing
greater than (m + 1) / (m + 2) are below those of width
at most (m + 1) / (m + 2)
5: Pack rectangles of width at most 1 / (m + 2) into the region R
using the FFDH algorithm such that no rectangle overlaps the top
of those packed up
6: It was found by adding the height of each strip. Join
Apparently, this algorithm was sharpened by a certain nature of the input data, well, any practical situation has the right to exist. Now you will understand everything yourself. Sorted, as usual, by non-increasing height, the rectangles are combined into pairs so that the difference in height in the pair does not exceed the specified proportion, usually 0-10%. Another condition is that their total width fit into the strip. The resulting "super-rectangles" are packed together with the remaining ones without a pair using NFDH and FFDH, the best solution is chosen.
There is a variation of this algorithm, when the rectangles are sorted by width and vertically combined, with the same condition of maximum deviation of width in a pair by a specified number of percent.
Algorithm Join
Input: The number of rectangles to be packed n,
the dimensions of the rectangles
{w (Li); h (Li)}, the constant gamma as a
percentage and the strip width W.
Output:
1: Sort the rectangles in order of non-increasing height such that h (L1) ≥ h (L2) ≥ ... ≥ h (Ln)
2: j = 1
3: while j + 1 ≤ n do
4: if (h (Lj) - h (Lj + 1)) / h (Lj) * 100 <gamma
and w (Lj) + w (Lj + 1) ≤ W then
5: w (Lj) + = w (Lj + 1)
6: j + = 2
7: else
8: j ++
9: end if
10: end while
11: Execute the NFDH and FFDH
12: From the best solution to the original instance
13: It was found by adding the height of each strip. Floor Ceiling No Rotation
If you are still perplexed about the remaining space, then this algorithm is for you. The rectangles are sorted by non-increasing height (unexpected, yes?) And the BFDH algorithm is applied with some modifications. Each level has a "floor" (floor) and "ceiling" (ceiling). As long as possible, the rectangles are packed on the "floor" from left to right. When the place ends, an attempt is made to pack to the "ceiling" from right to left; if there is no space on the ceiling, then only a new level begins. In the best traditions of BFDH, at every step all levels are viewed - first the “floor”, then the “ceiling” - for the presence of the most suitable place. Packaging, as you can see, is not bad. The method successfully packs the smallest rectangles along the “ceilings”.
FCNR algorithm
Input: The number of rectangles to be packed n,
the dimensions of the rectangles
{w (Li); h (Li)} and the strip width W.
Output:
1: Sort the rectangles in order of non-increasing height such that h (L1) ≥ h (L2) ≥ ... ≥ h (Ln)
2: for i = 1..n do
3: if Li is ceiling feasible then
4: pack Li on ceiling with minimum residual space
5: else [Li is not ceiling feasible]
6: if Li is floor feasible then
7: pack Li on the floor with minimum residual space
8: else [Li is not floor feasible]
9: level ++;
10: end if
11: end if
12: end for
13: It was found by adding the height of each strip. Sleator
It is time for "flat" algorithms, without division into levels. The Sleator algorithm uses the intuitive principle of packing a backpack: fold the largest items to the bottom and fill them up with small ones. Here's what it looks like. The widest are chosen from the rectangles, half of the strip is wider, as you have already guessed, and chaotically fit each other with alignment on the left edge. The rest are sorted by non-ascending height and begin to stack one after the other, from left to right, from the top to the already laid ones. As soon as their total width exceeds half the width of the strip, the rest are spread over each other, either to the left (starting from the left edge of the strip), then to the right (from the middle), according to the principle “where it is less at the moment”. As can be seen from the figures, this method makes it easier to stack books than boxes.
Algorithm Sleator
Input: The number of rectangles to be packed n,
the dimensions of the rectangles
{w (Li); h (Li)} and the strip width W.
Output:
1: Partition L into two sublists of L1 and L2
of width greater than 1/2 and at most 1/2 respectively.
2: Stack all the rectangles in L1 left justified on top of
one another starting Compute hstack
3: Packing will continue above Hstack
4: Sort the rectangles in L2 according to non-increasing height
such that h (Li) ≥ h (Li + 1) for i <n
5: Let it be a tallest rectangle in list L2.
6: Pack the rectangles, left justified from the left to the right
it is not clear
a rectangle or all of the rectangles have been packed
7: Partition the line with a line
There is possibly one rectangle
by the vertical line.
8: Rectangle on the right
(resp. left) edge (left. resp.) edge
is it
by the vertical line
9: while there are unpacked rectangles do
10: Draw horizontal lines of length half across
whose height is Hleft and Hright
11: All subsequent packing will either be on the left
or right segment of the strip
12: Select the segment with minimum height and pack
from the strip to the strip
vertical line until all rectangles have been
packed or there is a rectangles which does not fit
13: end while
14: print H = max {Hleft; Hright} Burke
Again, the smooth algorithm for which an additional “height map” is introduced:
| | | _ _ ___ | | | | | | _ | _ | | | | | | _ | | | | | | _ _ _ _ _ _ _ _ | .. | _ | _ | _ | _ _ | _ | _ _ | 0 0 0 0 0 0 0 0 1 0 3 3 3 3 3 3
This is an array by which the least populated areas and their width can be tracked as the band fills up. At the beginning it is filled with zeros. The rectangles are sorted by non-increasing, suddenly, widths. Then, at each step of the algorithm:
1. Calculates the position of the lowest area - the index of the minimum value of the array;
2. The most suitable rectangle is selected - firstly, which fits in this area, secondly, as much as possible filling it in width;
3. If a suitable rectangle is found, it is placed in this area in one of the ways:
3.1 On the left edge of the area;
3.2 Closer to a higher neighbor, if one of the neighbors is the edge of a strip, then closer to the edge;
3.3 Closer to a lower neighbor, if one of the neighbors is the edge of the strip, then farther from the edge. To the array values ​​corresponding to the width of the rectangle, its height is added.
4. If there is no suitable rectangle, the area is “filled” by aligning its height to the height of the nearest edge.
Did you already want to write a Tetris bot using this algorithm?
Burke algorithm
Input: The number of rectangles to be packed n,
the dimensions of the rectangles
{w (Li); h (Li)} and the strip width W.
Output:
1: Sort the rectangles according to non-increasing width such that w (Li) ≥ w (Li + 1) ≥ .. ≥ W (Ln)
2: for each placement policy
(leftmost, tallest neighbor, smallest neighbor) do
3: while Rectangles not packed do
4: find lowest gap
5: if w (Li) ≤ GapWidth then
6: place best fitting rectangle using placement policy
7: raise height
8: else
9: raise gap to height
10: end if
11: end while
12: end for
13: The height of the packing
14: Compare the best solution Who is better?
The result of each algorithm is the level of fullness of the band; the smaller, the better. It can be estimated by the optimal attitude towards it:
Let's compare the obtained results for the two given sets of source data:
| Optimal decision | NFDH | FFDH | Bfdh | KP01 | SF | JOIN | FCNR | Sleator | Bruke | |
|---|---|---|---|---|---|---|---|---|---|---|
| Set 1 | 149 | 0.65 | 0.71 | 0.71 | 0.71 | 0.75 | 0.61 | 0.83 | 0.68 | 0.72 |
| Set 2 | 140 | 0.66 | 0.77 | 0.77 | 0.78 | 0.77 | 0.70 | 0.84 | 0.51 | 0.71 |
We see that Floor Ceiling won for both data sets. It may be noted that Sleator showed a much better result for the first set, and Join, on the contrary, is more suitable for the second. But all this is nothing more than statistics.
Epilogue
Due to its simple formulation, the task of binary packaging can be pulled to a huge number of practical applications: directly to the packaging of objects or the cutting of material, the distribution of funds, the planning of tasks on clusters, etc. There are few refined tasks in life, but, having limited some conditions, it is possible to reduce the situation to a beautiful mathematical model having a good solution that can be achieved in polynomial time. And once, as a result of the butterfly effect, the discarded conditions will weigh heavily and the decision will fly to all the Nameless. Because of such assumptions, the world is imperfect.
Something I was distracted. In the next part, I hope to talk about the online version of the problem and the shelf algorithms. Good luck!
Sources of inspiration:
Nthabiseng Ntene An Algorithmic Approach to the 2D Oriented Strip Packing Problem
David Pisinger Knapsack problem
Survey on two-dimensional packing
Level Algorithms and Shelf Algorithms (careful, design-tear out eyes)
Code (Qt):
Algorithms packager.h packager.cpp
Gui window.h window.cpp renderarea.h renderarea.cpp main.cpp
UPD: Online algorithms
Source: https://habr.com/ru/post/136225/
All Articles