一类难解0/1背包问题的有效搜索算法  

Efficient Search Algorithm for a Class of Hard 0/1 Knapsack Problem

作　　者：罗小虎[1] 吕强[1] 钱培德[1] 

机构地区：[1]苏州大学计算机科学与技术学院,苏州215006

出　　处：《计算机工程》2010年第17期195-197,共3页Computer Engineering

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]