Simple but efficient approaches for the collapsing knapsack problem

✍ Scribed by Ulrich Pferschy; David Pisinger; Gerhard J. Woeginger

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 596 KB
• Volume: 77
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00134-5

✦ Synopsis

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.