The integer unlimited-supply Knapsack problem is definined as maximization of the combined weight of items of several types, respecting the constraint on their combined weight. Given a set of n integer and non-zero weights (w1, w2, ..., wn) and integer values (v1, v2, ..., vn), and a weight boundary (b), the task is to maximize the value of x0 = v1 x1 + v2 x2 + ... + vn xn, provided that the constraint w1 x1 + w2 x2 + ... + wn xn <= b holds. A typical dynamic programming algorithm runs in O(n b) space and time. The report presents a different algorithm that allows solving all instances of Knapsack problem for large enough boudaries in O(n w1) time, which is typically significantly smaller than O(n b).

Pre-2018 CSE ID: CS2004-0783

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

A Knapsack problem is to select among n types of items of various values and weights to fill a knapsack of weight-carrying capacity b. The problem is NP-complete and has a dynamic programming algorithm of time complexity O(n b). If the given b is large, the optimum solution is periodic with its period equals to the weight of the best item. We introduce a new O(n 2 w 1 log (n w1)) algorithm that solves all instances b of the problem for a given set of items, where w1 is the weight of the best item and is usually much smaller than b. We conjecture that there are many other NP-complete number problems whose optimum solutions also become periodic for large instances and hence can be solved by similar algorithms.
Keywords: Knapsack, dynamic programming, shortest-path, NP, pseudo-polynomial

Pre-2018 CSE ID: CS2004-0775