A COST-OPTIMAL SEARCH TECHNIQUE FOR THE KNAPSACK-PROBLEM

The knapsack problem is known to be a typical NP-complete problem, whi ch has 2(n) possible solutions to search over. Thus a task for solving the knapsack problem can be accomplished in 2(n) trials if an exhaust ive search is applied. In the past decade, much effort has been devote d in order to reduce the computation time of this problem instead of e xhaustive search. In 1984, Karnin proposed a brilliant parallel algori thm, which needs O(2(n/6)) processors to solve the knapsack problem in O(2(n/2)) time; that is, the cost of Karnin's parallel algorithm is O (2(2n/3)). In this paper, we propose a fast search technique to improv e Karnin's parallel algorithm by reducing the search time complexity o f Karnin's parallel algorithm to be O(2(n/3)) under the same O(2(n/6)) processors available. Thus, the cost of the proposed parallel algorit hm is O(2(n/2)). Furthermore, we extend this search technique to the c ase that the number of available processors is P = O(2(x)), where x gr eater than or equal to 1. From the analytical results, we see that our search technique is indeed superior to the previously proposed method s. We do believe our proposed parallel algorithm is pragmatically feas ible at the moment when multiprocessor systems become more and more po pular.