说明：  利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2n/4)1− ε个并行处理机单元,0≤≤ε1,O(2n/2)个存储单元,在O(2n/4(2n/4)ε)时间内求解n维背包问题,算法的成本为O(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.
(The use of sub-rule strategy, a shared memory based on the SIMD model of parallel computer algorithm knapsack problem. Algorithm allows the use of O (2n/4) 1-ε of parallel processor units, 0 ≤ ≤ ε1, O (2n/2 ) a memory cell, in the O (2n/4 (2n/4) ε) time for solving n-dimensional knapsack problem, algorithm of cost O (2n/2). the proposed algorithm with the existing literature shows that the conclusions, The algorithm improves the corresponding results of the literature is the cost of solving the knapsack problem the optimal parallel algorithm. At the same time, also pointed out that the main conclusions of the relevant literature mistake.)