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

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