基于贪心程度和区域界定的预期效率模型求解0-1背包问题

• 作者: 张永翼 苏爱东 高维珉
• 来源期刊: 计算机应用研究
• 关键词: 0-1 背包问题 贪心程度 区域界定 预期效率 最优解 目标函数值
• 年，卷（期）: 2015,（11）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 3304-3308
• 页数: 5页
• 分类号: TP181|TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2015.11.023

摘要

对现有的求解0-1背包问题的预期效率模型进行了改进，提出了一种基于贪心程度和区域界定的预期效率模型。贪心程度决定着提前装入背包的物体个数，区域界定决定了动态预期效率计算公式所执行的次数。针对该方法求解0-1背包问题，给出相应的定理证明了方法的正确性。仿真实验表明，该算法能够解决0-1背包问题。与已有动态预期效率算法相比，具有明显的高效性；与萤火虫群算法相比，算法亦具有较快的收敛速度。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	苏爱东		3	15	3.0	3.0
2	张永翼		3	14	3.0	3.0
3	高维珉		2	9	2.0	2.0