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

摘要

When using dynamic programming algorithm to solve 0-1 knapsack problem, its time complexity and space complexity both are O(nC). Its space complexity is not acceptable in case of large scale problem. From the recursive equations for computing optimal value of 0-1 knapsack problem, Memory Efficient Dynamic Programming(MEDP) is proposed. In order to conquer the drawback of MEDP, a new hybrid algorithm is put forward, which combines divided-and-conquered strategy with it and whose time complexity is O(nC). The hybrid algorithm eliminates the backtracking step, while it can find the goods put into the knapsack under the space complexity O( [n/d] + C), where d is the word length of computer. Experimental result demonstrates that the algorithm works identically with the theory.%用动态规划算法求解0-1背包问题的时空复杂度为O(nC).这个空间复杂度在求解大规模问题上是不可接受的.从计算0-1背包问题最优值的递归方程出发,给出高效利用内存的动态规划算法.为了克服内存高效的动态规划算法带来的缺点,设计新混合算法求解0-1背包问题.该新混合算法的时间复杂度为O(nC)；它消除了回溯阶段,并且为求得放入背包的物品所使用的空间复杂度仅为O([n/d]+C),其中d为计算机字长.实验结果表明,混合算法的工作效率与理论分析相同.