背包问题的二分网格算法

摘要：

本文介绍了属于NP难问题的无界背包问题的一种新的精确算法,基于问题的几何结构通过二分搜索方法不断减小解空间,最终直接求出问题的最优效益值和最佳装包方案.当待装入包中的物品数量固定时,算法的时间复杂性为线性时间,初步解决了求解当前呈指数增长背包实例时存在的困难,实验中各种数据实例证明与常用的MTU2和EDU相比,该新算法在理论上是可行的.

关键词：背包问题、计算复杂性、NP-难、二分网格

所属期刊栏目：32

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60273075;国家高技术研究发展计划863计划863-306ZD-11-01-06

在线出版日期：2005-10-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：217-220