Unbounded knapsack problem: Dynamic programming revisited

We present EDUK, an efficient dynamic programming algorithm for the unbounded knapsack problem. It is based primarily on a new and useful dominance relation, called threshold dominance, which is a strict generalization of all the previously known dominance relations. We show that combining it with a sparse representation of the iteration domain and the periodicity property leads to a drastic reduction of the solution space. We present computational experiments with various data instances to validate our ideas and demonstrate the efficiency of EDUK vis-à-vis the well-known exact algorithm MTU2.