Dynamic Programming Revisited: Improving Knapsack Algorithms |
| |
Authors: | U. Pferschy |
| |
Affiliation: | Department of Statistics and Operations Research, University of Graz, Universit?tsstr. 15, A-8010 Graz, Austria, e-mail: pferschy@kfunigraz.ac.at, AT
|
| |
Abstract: | The contribution of this paper is twofold: At first an improved dynamic programming algorithm for the bounded knapsack problem is given. It decreases the running time for an instance with n items and capacity c from to , which is the same pseudopolynomial complexity as usually given for the 0--1 knapsack problem. In the second part a general approach based on dynamic programming is presented to reduce the storage requirements for combinatorial optimization problems where it is computationally more expensive to compute the explicit solution structure than the optimal solution value. Among other applications of this scheme it is shown that the 0--1 knapsack problem as well as the bounded knapsack problem can be solved in time and space. Received: October 15, 1998; revised March 10, 1999 |
| |
Keywords: | AMS Subject Classifications:90C10 90C39. |
本文献已被 SpringerLink 等数据库收录! |
|