Department of Computer Science & Engineering

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.

Pre-2018 CSE ID: CS2004-0794