计算机科学 ›› 2005, Vol. 32 ›› Issue (6): 217-220.
• • 上一篇 下一篇
李庆华 潘军 李肯立
出版日期:
发布日期:
Online:
Published:
摘要: 本文介绍了属于NP难问题的无界背包问题的一种新的精确算法,基于问题的几何结构通过二分搜索方法不断减小解空间,最终直接求出问题的最优效益值和最佳装包方案。当待装入包中的物品数量固定时,算法的时间复杂性为线性时间,初步解决了求解当前呈指数增长背包实例时存在的困难,实验中各种数据实例证明与常用的MTU2和EDU相比,该新算法在理论上是可行的。
关键词: 背包问题 网格算法 二分 NP难问题 时间复杂性 精确算法 搜索方法 几何结构 指数增长 解空间 效益值 新算法 实例 无界 最优 数据
李庆华 潘军 李肯立. 背包问题的二分网格算法[J]. 计算机科学, 2005, 32(6): 217-220. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2005/V32/I6/217
Cited