A HEURISTIC ALGORITHM BASED ON EXPECTATION EFFICIENCY FOR 0-1 KNAPSACK PROBLEM

摘要

0-1 Knapsack Problem (KP01) is a classical NP-hard problem and it playsan important role in real-world applications. In this paper, we propose a heuristic algorithmbased on Expectation Efficiency, Increasing rate of profit and Improved greedystrategy (EEli) to get approximate solution of KP01. (i) Some items are selected withgreedy strategy and put into knapsack, (ii) We propose expectation efficiency strategy andincreasing rate of profit strategy to determine which items are loaded into knapsack fromthe remaining items, (in) We limit the size of items to improve calculation efficiencyof expectation efficiency and increasing rate of profit, (iv) An improved greedy strategyis devised to solve the special KP01 from the perspective of variation coefficient. Thecomputational 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.