The Parallel Processing Approach to the Dynamic Programming Algorithm of Knapsack Problem

This paper aims at comparing the serial, shared memory parallelization, and distributed memory parallelization of the dynamic programming algorithm for the Knapsack Problem. Knapsack Problem is one of the most popular optimization problems. This is the decision-making problem and uses for real-world situations such as business projects, airline cargo business, cryptography, and decision-making industry processes, etc. The algorithm under consideration is the table- based dynamic programming algorithm based on Bellman's optimality principle. We used the C++ programming language. To solve this problem on shared memory systems, we used the OpenMP. For the distributed memory parallelization, we employed the MPI The structure of the algorithm, the data distribution, synchronization, and communication schemes are explained in detail. Extensive experiments for the developed algorithms were carried out. The obtained results helped to make a comparative analysis of the developed algorithms.