关键词: 矩形排样问题, 动态规划算法, 隐枚举, 五块模式

Abstract: It is widely appears in manufacturing field of plate segmentation and the logistics industry
field of pallet loading that how to finding a maximal layout for identical small rectangles on a larger
rectangle. The large rectangle is divided into five blocks using five-block mode, then the problem is
solved to arrange the identical small rectangular into each blocks. Firstly, the dynamic programming
method is used to generate the entire layout of rectangular in blocks in once. Then, the enumeration
method is used to consider all of five blocks combination. The combination is selected to generate the
final pattern which have the maximal number of rectangular. Several examples are used to test the
proposed algorithm, and comparing the algorithm with other 4 kinds of single layout algorithm. The
experimental results show that the algorithm is efficient in both the layout utilization rate and the
cutting process with a reasonable computing time.

Key words: rectangle packing problem, dynamic programming algorithm, implicit enumeration, five
block mode