.png){kind=icon}
.png){kind=icon}
Return
Dynamic programming revisited: Improving knapsack algorithms
.png){kind=icon}
PRE
AI
DOI：10.1007/s006070050042.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 O(nc log c) to O(nc), 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 O (nc) time and O (n + c) space.
Keywords:
knapsack
bounded knapsack
dynamic programming