UKP5: A New Algorithm for the Unbounded Knapsack Problem

摘要

In this paper we present UKP5, a novel algorithm for solving the unbounded knapsack problem. UKP5 is based on dynamic programming, but implemented in a non traditional way: instead of looking backward for stored values of subproblems, it stores incremental lower bounds forward. UKP5 uses sparsity, periodicity, and dominance for speeding up computation. UKP5 is considerably simpler than EDUK2, the state-of-the-art algorithm for solving the problem. Moreover, it can be naturally implemented using the imperative paradigm, differently from EDUK2. We run UKP5 and EDUK2 on a benchmark of hard instances proposed by the authors of EDUK2. The benchmark is composed by 4540 instances, divided into five classes, with instances ranging from small to large inside each class. Speedups were calculated for each class, and the overall speedup was calculated as the classes speedups average. The experimental results reveal that UKP5 outperforms EDUK2, being 47 times faster on the overall average.