Research On The Parallel Algorithms Of0-1Knapsack Problem Based On Divide And Conquer

The0-1knapsack problem is well known to be NP-Hard problem. Now it isunlikely to be solved in polynomial time. Because of its importance in combinatorialoptimization and its varied practical applications in capital budgeting problem, cargoloading problem, cutting stock problem and computer cryptosystem, reducing thecomputing costs of solving this problem has great theoretical and realisticsignificance, and become a pressing need for scientists and scholars.Along with the gradual development of parallel computing, people are interestedin researching the parallel algorithms of the0-1knapsack problem. The parallelalgorithms for0-1knapsack problem can be classified into two methods: the dynamicprogramming and the divide and conquer. Now, the dynamic programming has beensuccessfully applied to the parallel algorithms for the0-1knapsack problem, and hasemerged in a lot of research. But to our knowledge the parallel method of divide andconquer mainly has applied to solving the subset problem, and not been appliedsuccessfully to solving the0-1knapsack problem.Therefore, based on thorough studyof the PRAM parallel computing model and the parallel method of divide and conquer,this paper introduces the three list serial algorithm and the two list serial algorithm forthe0-1knapsack problem, and base on EREW PRAM parallel computing modelproposes two new parallel algorithms for the0-1knapsack problem, named the threelist parallel algorithms and the two list parallel algorithms, then analyzes andcompares the performance of the algorithms in theory. The former take up lessmemory storage space than the latter, and the latter is both the lowest upper-boundtime and without memory conflicts if only quantity of objects is considered in thecomplexity analysis for the0-1knapsack problem.In the end, this paper separately use OpenMP and MPI+OpenMP programmingmodel to design experiment of the two list parallel algorithms for0-1knapsackproblem, and test the experiment repeatedly. Thus compares the difference of thetime-consuming and parallelization performance of the algorithms under the differentmulti-core circumstances. The experiment results show that our proposed parallelalgorithms not only have good feasibility to reduce the execution time, but alse havebetter speedup and parallel efficiency.