背包问题的二分网格算法

• 作者: 李庆华 李肯立 潘军
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 背包问题 计算复杂性 NP-难 二分网格
• 年，卷（期）: 2005,（6）
• 所属期刊栏目: 软件工程
• 页码范围: 217-220
• 页数: 4页
• 分类号: TP3
• 字数: 5833字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2005.06.061

摘要

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