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.

摘要：

为了进一步优化0-1背包问题的解，就背包容量、物体个数、物体重量、物体价格和物体性价比之间的关系进行深入的分析研究，构建了一个基于数学理论的线性拟合模型，与预期效率相结合，给出了一个解决0-1背包问题的混合算法。给出了三组实验，测试ρ<0.7时的算例，当背包容量改变时，与萤火虫群算法相比，该算法提高了目标函数值的收敛速度，同时节省了存储空间；与单纯的预期效率算法相比，该算法能够求得最优解，而单纯的预期效率算法则不能。实验结果表明，预期效率和线性拟合混合算法具有合理性及准确性，该算法能够应用于解决实际的0-1背包问题。