Open AccessAn Efficient Heuristic Algorithm for Solving 0-1 Knapsack Problem
Author(s) -
Hong Yang,
Xiong Guo
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1865/4/042009
Subject(s) - knapsack problem , continuous knapsack problem , mathematical optimization , greedy algorithm , heuristic , convergence (economics) , degree (music) , efficient algorithm , mathematics , computer science , algorithm , physics , acoustics , economics , economic growth
The model for 0-1 knapsack problem based on greedy strategy and expectation efficiency has some advantages, e.g., quick convergence and low complexity, but it also inherently exists some limitations to be enhanced and improved, such as the restricted greedy and the overmuch calculation on expectation efficiency. To this end, an efficient algorithm is proposed to optimize the previous model. At first, the greedy degree is maximized, that is, some items are permanently loaded into knapsack in advance as many as possible. Then, the conventional expectation efficiency model is improved greatly, at the same time, the number of calculations with respect to expectation efficiency is decreased by ignoring some unnecessary items. Compared to the previous algorithm, the experimental results reveal that the proposed optimization algorithm has the significant advantages in time.