A General Algorithm for One-Dimensional Knapsack Problems

Abstract

This paper presents a reduction algorithm and a branch-search algorithm that, in sequence, allow the solution of sizeable problems of the form: maximize ∑ i=1 N c i x i , subject to ∑ i=1 N l i x i ≦ s and 0 ≦ x i ≦ b i and integer, 1 ≦ i ≦ N. The reduction algorithm is proportional to N in space and proportional to N ∑ i=1 N b i in time. The branch-search algorithm's space requirement is linear in N. Computational experience with these algorithms is presented.