AN EFFICIENT DYNAMIC PROGRAMMING PARALLEL ALGORITHM FOR THE 0-1 KNAPSACK PROBLEM

摘要

An efficient parallel algorithm for the 0-1 knapsack problem is presented. The algorithm is based on dynamic programming in conjunction with dominance of states techniques. An original load balancing strategy which is designed in order to achieve good performance of the parallel algorithm is proposed. To the best of our knowledge, this is the first time for which a load balancing strategy is considered for this type of algorithm. Finally, computational results obtained with an Origin 2000 supercomputer are displayed and analyzed.