A PARALLEL ALGORITHM FOR THE KNAPSACK PROBLEM WITH MEMORY/PROCESSOR TRADEOFF M²P = O(2^n/2)

The purpose of this paper is to suggest a new parallel algorithm for the knapsack problem. The design of the proposed parallel algorithm is based on a shared memory SIMD machine with a heap tree data structure. It can solve a general n-component knapsack problem in time O(2^n/2) with memory-processor tradeoff M²P = O(2^n/2). The proposed technique can have better performance in terms of cost as the number of processors needed can be offset by increasing memory space. The performance is compared with those of other algorithms to demonstrate its superiority. We believe that the proposed algorithm is pragmatically feasible at the moment when multiprocessor systems are gradually becoming popular.