%0 Journal Article
%T 背包问题的二分网格算法
%A 李庆华 潘军 李肯立？
%J 计算机科学
%D 2005
%X 本文介绍了属于np难问题的无界背包问题的一种新的精确算法，基于问题的几何结构通过二分搜索方法不断减小解空间，最终直接求出问题的最优效益值和最佳装包方案。当待装入包中的物品数量固定时，算法的时间复杂性为线性时间，初步解决了求解当前呈指数增长背包实例时存在的困难，实验中各种数据实例证明与常用的mtu2和edu相比，该新算法在理论上是可行的。
%K 背包问题网格算法二分np难问题时间复杂性精确算法搜索方法几何结构指数增长解空间效益值新算法实例无界最优数据
%U http://www.jsjkx.com/jsjkx/ch/reader/view_abstract.aspx?file_no=16191217&flag=1