Abstract: The rectangle-packing problem often appears in loading, timber cutting, very large scale integration design, etc. Many algorithms such as simulated annealing, genetic algorithm and other heuristic algorithms are proposed to solve it. This paper recommends an efficient greedy algorithm according to ten-thousand-year experience and wisdom of human being. Twenty-one public instances are tested by the algorithm developed. The average trim loss and runtime is 0.28% and 17.86s respectively. Furthermore, 8 instances are achieved optimum solutions. Experimental results demonstrate that the algorithm developed is fairly efficient for solving rectangle-packing problem.

Key words: Rectangle packing, Greedy algorithm, Corner-occupying action

摘要： 在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题，国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验，提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试，所得结果的平均面积未利用率为0.28%，平均计算时间为17.86s，并且还得到了其中8个实例的最优解。测试结果表明，该算法对求解矩形packing问题相当有效。

关键词: 矩形packing, 贪心算法, 占角动作