摘要： 针对一类难解0/1背包问题，给出背包最大价值与物品集中元素的组合特性，在价值密度比贪心策略的基础上，采用组合交叉搜索策略设计一个快速搜索算法——ZHKnap。实验表明，在多项式时间复杂度内得到的解的质量优于目前算法的结果，证明最优解与元素的重量和价值参数的大小分布无关，而只与元素的重量及背包零头的组合相关。

关键词: 0/1背包问题, 价值密度比, 搜索算法

Abstract: As for a class of hard 0/1 knapsack problem, this paper describes the combinatorial correlation between the maximum value and the items in the object set and proposes an algorithm named ZHKnap that applies the calculation of combined cross based on the greedy policy of the non-increasing profit-to-weight ratio. Experimental results show that ZHKnap outperforms state-of-the-art algorithm in polynomial time in terms of the average solution quality and prove that the optimum solution has no relation with both the coefficient of the items and the gap between the integer optimum and the linear optimum, instead, such solutions only relate to the combination of the items’ weight and the fraction derived with the greedy policy.

Key words: 0/1 knapsack problem, profit-to-weight ratio, search algorithm

中图分类号: 

• TP18