作者：黄海; 李松斌二维装箱近似算法np难度启发式
摘要：2-Dstrippacking问题指将带有价值的矩形物品装入长宽固定的箱子中，使其装入的物品价值最大。基于装箱的期望目标ε，提出一种新的分组构造函数，结合装箱矩形特点计算出最优分组参数u并对矩形进行分类，同时对不同类别的矩形引入相应的数据结构，最后对不同类别矩形基于箱子X轴的u等分点进行填充，使其装入的物品价值最大。文中的主要贡献在于：提出了一种有效的分组构造函数；计算出了对应的最优分组参数u;简化了不同类别箱体的数据结构以及相应的装箱算法；特别地，在期望目标ε、多项式时间复杂度和至少装入（1-ε）OPT价值物品的情况下，可将所需箱体宽度从1＋ε减小到1，而高度保持不变。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
