背包问题的二分网格算法  

A Dimidiate Grid Algorithm for the Unbounded Knapsack Problem

作　　者：李庆华[1] 潘军[1] 李肯立[1] 

机构地区：[1]国家高性能计算中心

出　　处：《计算机科学》2005年第6期217-220,共4页Computer Science

基　　金：国家自然科学基金(60273075);国家863高科技发展计划(863-306ZD-11-01-06)资助

摘　　要：本文介绍了属于NP难问题的无界背包问题的一种新的精确算法,基于问题的几何结构通过二分搜索方法不断减小解空间,最终直接求出问题的最优效益值和最佳装包方案。当待装入包中的物品数量固定时,算法的时间复杂性为线性时间,初步解决了求解当前呈指数增长背包实例时存在的困难,实验中各种数据实例证明与常用的MTU2和EDU相比,该新算法在理论上是可行的。This paper presents a new exact algorithm for the unbounded knapsack problem, which is a famous NP- hard problem. It is based primarily on the basic geometric structure of the problem, by the tool of two-partition, the solution space of the problem is increasingly reduced until the optimal allocation of objects and optimal profits is di- rectly obtained. As the complexity of the algorithm is linear to the length of the input data when the number of items is fixed, it can preparatorily overcome the present hardness in solution of knapsack problems with exponentially grow- ing coefficients. The computational experiments with various data instances, comparing our new algorithm with the well-known MTU2 and EDUK are presented, and they demonstrate the theoretical performance of the proposed algo- rithm.

关 键 词：背包问题 网格算法 二分 NP难问题 时间复杂性 精确算法 搜索方法 几何结构 指数增长 解空间 效益值 新算法 实例 无界 最优 数据 

分 类 号：TP393.41[自动化与计算机技术—计算机应用技术] O224[自动化与计算机技术—计算机科学与技术]