论文部分内容阅读
装箱问题是组合优化中的一个经典问题，而此问题属于NP-难问题.由于其广泛的应用，寻找装箱问题的近似算法就成为研究的重点.最大效益装箱覆盖问题是装箱问题的推广，在现实生活中也有广泛的应用.
本文研究了新的装箱问题-最大效益装箱覆盖问题，我们得到如下结果：(1)此问题是NP-难的，并且对Aε>0，不存在近似值为(2-ε)的多项式时间算法；(2)设计出四个启发式算法；(3)当所有物品大小相同时，设计出一个线性时间内的动态规划算法求得最优解.
本文包括以下几章：
第一章：问题介绍，给出了经典一维装箱的一些相关研究成果.
第二章：给出了文中所出现的定义、概念和符号.
第三章：总结了箱子覆盖问题的一些相关研究结果，给出了最大效益装箱覆盖问题的线性规划形式，并对其困难性进行了分析，设计出四个启发式算法和在一种特殊情况下的动态规划算法.
最后，给出了相关结论以及未来的研究方向.
另外，本文给出了较为良好的计算机程序和具体的上机实验步骤.