查看文章

0-1 Knapsack Problem (KP01) is a classical NP-hard problem and it plays an important role in real-world applications. In this paper, we propose a heuristic algorithm based on Expectation Efficiency, Increasing rate of profit and Improved greedy strategy (EEII) to get approximate solution of KP01.(i) Some items are selected with greedy strategy and put into knapsack.(ii) We propose expectation efficiency strategy and increasing rate of profit strategy to determine which items are loaded into knapsack from the remaining items.(iii) We limit the size of items to improve calculation efficiency of expectation efficiency and increasing rate of profit.(iv) An improved greedy strategy is devised to solve the special KP01 from the perspective of variation coefficient. The computational experiments are done by comparing EEII with (i) Greedy Approximate Algorithm (GAA) and (ii) Greedy Degree and Expectation Efficiency (GDEE) algorithm, and the results show that EEII has good performance to solve KP01.