A PARALLEL ALGORITHM FOR THE KNAPSACK-PROBLEM USING A GENERATION AND SEARCHING TECHNIQUE

The purpose of this paper is to propose a new parallel algorithm for t he knapsack problem. We develop a generation and searching technique t o derive the desired two ordered lists in the preliminary process of t he general knapsack problem. The proposed parallel algorithm is develo ped on the basis of an SIMD machine with shared memory. The algorithm needs O(2n/4) memory and O(2n/8) processors to find a solution for the knapsack problem of n components in time O(2n/2). The proposed parall el algorithm has a cost of O(2(5n/8)) which is an improved result over the past researches.