求解0-1背包问题的一种新混合算法

摘要：

用动态规划算法求解0-1背包问题的时空复杂度为O(nC).这个空间复杂度在求解大规模问题上是不可接受的.从计算0-1背包问题最优值的递归方程出发,给出高效利用内存的动态规划算法.为了克服内存高效的动态规划算法带来的缺点,设计新混合算法求解0-1背包问题.该新混合算法的时间复杂度为O(nC)；它消除了回溯阶段,并且为求得放入背包的物品所使用的空间复杂度仅为O([n/d]+C),其中d为计算机字长.实验结果表明,混合算法的工作效率与理论分析相同.

关键词：0-1背包问题、动态规划、分治策略、混合算法

所属期刊栏目：48

分类号：TP391(计算技术、计算机技术)

在线出版日期：2012-04-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：50-53