Unbounded knapsack problems with arithmetic weight sequences

We investigate a special case of the unbounded knapsack problem in which the item weights form an arithmetic sequence. We derive a polynomial time algorithm for this special case with running time O(n8), where n denotes the number of distinct items in the instance. Furthermore, we extend our approach to a slightly more general class of knapsack instances.

► The paper solves a natural special case of the knapsack problem.
► The paper unifies several ideas and methods from the area.
► The paper uses an IP-formulation in a novel way.