Abstract
The collapsing knapsack problem is a generalization of the ordinary knapsack problem, where the knapsack capacity is a non-increasing function of the number of items included. Whereas previous papers on the topic have applied quite involved techniques, the current paper presents and analyzes two rather simple approaches: One approach that is based on the reduction to a standard knapsack problem, and another approach that is based on a simple dynamic programming recursion. Both algorithms have pseudo-polynomial solution times, guaranteeing reasonable solution times for moderate coefficient sizes. Computational experiments are provided to expose the efficiency of the two approaches compared to previous algorithms.
Original language | English |
---|---|
Pages (from-to) | 271-280 |
Journal | Discrete Applied Mathematics |
Volume | 77 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1997 |