Abstract:

In order to do further optimization on 0-1 Knapsack Problem (KP), the relationship among the backpack capacity, the number of objects, the weight of object, the price of object and the cost performance of object were analyzed, a linear fitting model based on mathematical theory was determined, and a hybrid algorithm for 0-1 KP was proposed with the expected efficiency. Three groups of experiments were given. For those examples with ρ<0.7, when the backpack capacity was changed, in comparison with artificial glowworm swarm algorithm, the proposed algorithm improved convergence speed of the objective value and saved the storage space; In comparison with the algorithm of absolute greedy and expected efficiency, the proposed algorithm got the optimal solution. The results prove that this hybrid algorithm is reasonable and exact, and it can be used widely to solve 0-1 KP.