论文部分内容阅读
2-Dstrippacking问题指将带有价值的矩形物品装入长宽固定的箱子中,使其装入的物品价值最大。基于装箱的期望目标ε,提出一种新的分组构造函数,结合装箱矩形特点计算出最优分组参数u并对矩形进行分类,同时对不同类别的矩形引入相应的数据结构,最后对不同类别矩形基于箱子X轴的u等分点进行填充,使其装入的物品价值最大。文中的主要贡献在于:提出了一种有效的分组构造函数;计算出了对应的最优分组参数u;简化了不同类别箱体的数据结构以及相应的装箱算法;特别地,在期望目标ε、多项式时间复杂度和至少装入(1-ε)OPT