Abstract: The rectangle and circle packing problem is concerned with packing a subset of different size rectangles and circles into a rectangular container, with the objective of maximizing the container’s area usage. It has many industrial applications, such as very large scale integration design, sewing, glass cutting, etc. Some popular algorithms can be utilized to solve it, for example, the simulated annealing and the genetic algorithm. However, These algorithms are time consuming and the performance is not satisfying. In this paper, a maximum caving degree algorithm is recommended according to the ten-thousand-year experience and wisdom of human being. We have applied three randomly generated instances to the algorithm developed. The average container’s area usage is 90.80% with an average runtime of 8.38 seconds. Experimental results demonstrate that the algorithm developed is fairly efficient for solving the rectangle and circle packing problem.

Key words: Packing, Rectangle and circle, Corner-occupying action, Caving degree

摘要： 在超大规模集成电路设计，裁缝裁剪布料，玻璃切割等工作中提出了矩形和圆形装填问题，即把不同大小的矩形块和圆饼装入一个矩形容器中，以最大化容器的面积利用率为优化目标。对这一问题，可采用模拟退火，遗传算法等国际流行算法进行求解，但这些方法计算时间较长，计算结果的优度也不甚理想。本文利用人类的智慧和他们近万年以来形成的经验，提出一种求解此问题的最大穴度算法。并对3个随机生成的测试实例进行了实算测试，所得结果的平均面积利用率为90.80%，平均计算时间为8.38秒。测试结果表明，本文算法对求解矩形和圆形装填问题是行之有效的。

关键词: 装填, 矩形和圆, 占角动作, 穴度