Sage Algorithms for Knapsack Problem

Leo Landa
CS2004-0794
June 18, 2004

We attack the unbounded integer knapsack problem, known to be NP-complete. The state-of-the-art algorithms for precise solutions are pseudo-polynomial with respect to n (the number of types of items available) and b (the capacity of the knapsack). With reasonable encoding, those algorithms are exponential with respect to the bits of encoding due to the presence of b. In practical settings, the boundary constraint b can be quite large with respect to the rest of the values in the problem statement, and becomes a dominating factor in both time and space complexity. We present different algorithms for solving knapsack problems that are not dependent on the value of boundary in the original problem. These algorithms allow building useful pre-solution information about a particular instance of a knapsack problem (boundary excluded), which later be used in combination with any boundary to generate a final solution in polynomial time. Specifically, the Sage-2D algorithm shown provides pre-solution information for sufficiently large boundaries in O(nw1) time and space complexity (where w1 is the weight of the best item), and the Sage-3D algorithm shown provides pre-solution information for any boundaries in O(nw1v1) time and space complexity (where w1 is the weight of the best item, and v1 is the weight of the best item). This type of approach has two advantages over the state-of-the-art algorithms. Firstly, even though the pre-solution algorithms are pseudo-polynomial with respect to the itemsí weights and values, they do not depend on the value of the boundary constraint b, which makes solving a large class of practical problems significantly easier (requiring less time and space). Secondly, this approach allows solving any number of knapsack problems with the same setup and varying boundary constraint in polynomial time, thus reducing the overhead of solving many knapsack-based practical problems. We conjecture that there are many more NP-complete problems that can also be solved through a pseudo-polynomial pre-solution and polynomial final solution.


How to view this document


The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, techreports@cs.ucsd.edu.


[ Search ]


NCSTRL
This server operates at UCSD Computer Science and Engineering.
Send email to webmaster@cs.ucsd.edu