Back to Search
Start Over
An improvement of dynamic programming to solve knapsack problem using multi-core system.
- Source :
-
AIP Conference Proceedings . 10/25/2022, Vol. 2398 Issue 1, p1-8. 8p. - Publication Year :
- 2022
-
Abstract
- The 0/1 Knapsack Problem (KP) is one of the problems in optimization where a set of items with given benefit and weights.The aim is to select a subset of the items in order to maximize the total benefit without exceeding the knapsack capacity. Nowadays, it becomes a big dilemma due to the explosion in the amount of datasets. In this paper, P(KD)P algorithm has been proposed and performed. For effectively calculating the KM matrix using multi- core system, an improved approach of the DP_KP algorithm has been considered. The proposed scheduling and partitioning approaches have accomplished a significant enhancement to the overall performance. Executions were implemented on corei7 with (8 cores). It outperforms sequential KP_DP more than 16-fold speedup and (KD)P more than 5-fold speedup. Its efficiency reaches 0.316, 0.0829 and 0.0979 over the KP_DP, (KD)P, and P(KD)P respectively. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0094243X
- Volume :
- 2398
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- AIP Conference Proceedings
- Publication Type :
- Conference
- Accession number :
- 159872607
- Full Text :
- https://doi.org/10.1063/5.0093571