A Minimal Algorithm for the Bounded Knapsack Problem
A Minimal Algorithm for the Bounded Knapsack Problem
复制标题
DOI：
10.1007/3-540-59408-6_44
复制
发表时间：
1995-05
期刊：
影响因子：
--
通讯作者：
David Pisinger
中科院分区：
文献类型：
--
作者：
David Pisinger
有界背包问题（BKP）是0-1背包问题的推广，其中每种物品类型的可用数量是有界的。目前最有效的BKP算法将数据实例转化为等价的0-1背包问题，并通过专门的算法高效地求解。然而，本文证明，该变换引入了许多相似的加权项，导致0-1背包问题的非常困难的实例。为了避免这些问题，提出了一种通过动态规划解决扩展核心问题的专用算法，使枚举项目类型的数量最少。分类和还原是根据需要完成的，因此预处理的工作量很小。与BKP的其他算法相比，本文提出的算法使用更严格的约简，枚举的项目类型也少得多。计算实验表明，本文提出的算法优于所有先前发表的BKP算法。
The Bounded Knapsack Problem (BKP) is a generalization of the 0–1 Knapsack Problem where a bounded amount of each item type is available. The currently 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 similar weighted items, resulting in very hard instances of the 0–1 Knapsack Problem. To avoid these problems, a specialized algorithm is proposed which 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 out-performs all previously published algorithms for BKP.