Optimizing the Knapsack Problem

Leo Landa
CS2004-0783
April 2, 2004

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).


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