Department of Computer Science & Engineering

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