A Dimidiate Grid Algorithm for the Unbounded Knapsack Problem
背包问题的二分网格算法

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.