论文部分内容阅读
本文研究了经典的一维装箱问题，由于装箱问题属于NP-完备性问题，不存在多项式时间的最优算法，我们设计了一种启发式算法来解决该问题，即“二分”装箱算法(简称算法BIF)，该算法利用了二分法的选择策略.
作为装箱问题的一个衍生问题，最小成本装箱覆盖问题在实际应用中有着很强的应用背景，是在最小基数装箱覆盖的基础上，给定箱子的大小、数目和每个物品的成本，要求从中选出一部分物品来覆盖所有箱子，并使得所选用物品的成本尽可能的小.在物品的大小满足一定的条件下，我们给出了该问题的一种启发式算法，叫做‘贪婪”装箱覆盖算法(简称算法GBC)，该算法利用了“贪婪”算法的选择策略.
本文包括以下几章：
第一章：回顾了问题的由来，给出了最近的一些相关研究成果.
第二章：给出了文中所出现的定义、概念和符号.
第三章：对一维装箱问题进行分析，并给出解决该问题的一个启发式算法.
第四章：对装箱问题的一种衍生问题：最小成本装箱覆盖问题进行分析，并给出解决该问题的一个启发式算法.
最后，给出了相关结论以及未来的研究方向.
另外，本文给出了较为良好的计算机程序和具体的上机实验的步骤.