背包问题的最优并行算法

利用分治策略,提出一种基于simd共享存储计算机模型的并行背包问题求解算法.算法允许使用o(2n/4)1-ε个并行处理机单元,0≤ε≤1,o(2n/2)个存储单元,在o(2n/4(2n/4)ε)时间内求解n维背包问题,算法的成本为o(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.