A minimal algorithm for the bounded knapsack problem

The Bounded Knapsack Problem (BKP) is a generalization of the 0–1 Knapsack Problem where a bounded amount of each item type is available. Currently, the most efficient algorithm for BKP transforms the data instance to an equivalent 0–1 Knapsack Problem, which is solved efficiently through a specialized algorithm. However, this paper demonstrates that the transformation introduces many similarly weighted items, resulting in very hard instances of the 0–1 Knapsack Problem. To avoid these problems, we propose a specialized algorithm that solves an expanding core problem through dynamic programming such that the number of enumerated item types is minimal. Sorting and reduction is done by need, resulting in very little effort for the preprocessing. Compared to other algorithms for BKP, the presented algorithm uses tighter reductions and enumerates considerably less item types. Computational experiments are presented, showing that the presented algorithm outperforms all previously published algorithms for BKP.