[带核的Bin-packing问题]

【带核的Bin-packing问题】.pdf浙江大学硕士学位论文 带核的Bin-packing问题浙江大学硕士学位论文 摘要 装箱问题是组合优化中最著名的问题之一,也是长期以来被广泛研究的一个 问题．它在生产实际中有广泛的应用背景,如在存储、集装箱等实际运用中起重 要作用．本文对一类特殊的装箱问题一带核装箱问题进行了分析和探讨,提出 了一个近似算法一FFD算法,给出了其渐近性能比 一的证明浙江大学硕士学位论文 第一章简介 本章简介了装箱问题已有的几种算法及相应的渐近性能比.S1.经典装箱问题 Bin-packing问题即装箱问题作为一个较为实际的问题已被提出许久,目前 也已获得了对它的较为美满的方案。所谓装箱问题,即给定有穷的“物品”集合 U分成k个不相交的子集U,U2,U,使得每一个U中的物品的体积之和不 超过1且k尽可能的小．我们可把每一个子集U.看作要装人一只单位容量的箱 子中的一组物品,其目标是把U中的物品装人尽可能少的箱子中,已经证明装箱问题是强NP完全的(它包含三元划分作为子情况),所以很少 有希望找到一个哪怕是关于它的伪多项式时间的最优化算法,但提出了
———— 文字由OCR识别(未校验)，可能存在错字；请以原始完整版为准。