一种用于求解0-1背包问题的动态伸缩算法

• 作者: 周涛 拓守恒
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 0-1背包问题 实数编码 启发式搜索算法 动态伸缩调整策略
• 年，卷（期）: 2012,（4）
• 所属期刊栏目: 研究、探讨
• 页码范围: 47-49
• 分类号: TP301.6
• 字数: 2269字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2012.04.014

摘要

针对0-1背包这个非确定多项式(NP)完全难题,提出一种新的启发式搜索算法来解决0-1背包问题.算法采用多维实数编码,将物品按价值/重量比从大到小排序装包,通过用启发式策略选择交换背包内和背包外物品的位置,采用动态伸缩策略调整背包大小,选取种群中部分优秀解进入下一代继续进行优化.通过5个背包实例进行测试,实验结果表明该算法收敛速度快、求解精度高,并且具有良好的稳定性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	拓守恒	陕西理工学院数学与计算机科学学院	55	591	12.0	22.0
2	周涛	宁夏医科大学理学院	49	522	10.0	21.0