一种全新的0-1背包问题的优化方法

• 来源期刊: 计算机应用研究
• 关键词: 0-1背包 动态预期效率 收敛速度 存储空间 适应范围
• 年，卷（期）: 2014,（4）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 997-1000
• 页数: 4页
• 分类号: TP18|TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2014.04.009

摘要

为了进一步优化难解背包问题，在传统理论基础上给出了一种基于动态预期效率的经济学模型，构造了一种全新的背包优化算法，并进行了单独仿真实验和对比实验仿真。实验表明，在同一类背包问题中，该算法优于贪心算法、回溯法、动态规划算法和分支限界算法；与萤火虫群算法对比，该算法较大程度地提高了收敛速度并节省了存储空间，收敛速度几乎是萤火虫群算法的10倍。最后，经过对20个背包问题的探究，验证了该算法的可行性，并确定了该算法的适应范围。