An Optimal Parallel Algorithm for the Knapsack Problem
背包问题的最优并行算法

A new parallel algorithm for the knapsack problem is proposed, in which the method of divide and conquer is adopted. Based on an CREW-SIMD machine with shared memory, the proposed algorithm needs O(2n/4)1-e processors, 0e1, and O(2n/2) memory to find a solution for the n-element knapsack problem in O(2n/4 (2n/4)e) time. The cost of the algorithm is O(2n/2), which is optimal and an improved result over the past researches. The wrong results in corresponding literatures are also pointed out in this paper.