- Main
Optimizing the Knapsack Problem
Abstract
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
Main Content
Enter the password to open this PDF file:
-
-
-
-
-
-
-
-
-
-
-
-
-
-