%0 Journal Article
%T A Dimidiate Grid Algorithm for the Unbounded Knapsack Problem<br>背包问题的二分网格算法
%A LI Qing-Hua
%A PAN Jun
%A LI Ken-Li
%A <br>李庆华
%A 潘军
%A 李肯立
%J 计算机科学
%D 2005
%I 
%X 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.
%K Knapsack problem
%K Computational complexity
%K NP-hard
%K Dimidiate grid<br>背包问题
%K 计算复杂性
%K NP-难
%K 二分网格
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=D4CF859EAA0DDACC&yid=2DD7160C83D0ACED&vid=9971A5E270697F23&iid=B31275AF3241DB2D&sid=F9F74EC1AA08A7B9&eid=1D67BE204FBF4800&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=12