0/1 Knapsack problem on hyper hexa-cell interconnection network

The knapsack problem is a well-known problem, and it has various types, such as 0/1 knapsack, fractional knapsack, bounded knapsack, and unbounded knapsack, and many applications, such as resource allocation, investment decisions, scheduling and planning, and architectures for localization. The knapsack problem is a combinatorial optimization problem where one must maximize the profit of objects in a knapsack without exceeding its capacity. In this paper, we design and implement a parallel dynamic programming algorithm to solve the 0/1 knapsack problem on a hyper hexa-cell interconnection network. This algorithm is referred to as the PDPK-HHC. The proposed algorithm is assessed analytically and through simulations based on multiple performance indicators such as communication time, computation time, overall execution time, speedup, efficiency, and solution quality across different dataset sizes and types. The best simulation results show that under the largest simulated configuration, the PDPK-HHC algorithm reached solutions matching the expected dynamic-programming optimum and achieved up to 505× speedup at 768 processors on a 512 MB dataset; at 12 processors, efficiency reached up to 95% under the tested conditions, demonstrating better performance than its sequential counterpart under the tested conditions.