A General Algorithm for One-Dimensional Knapsack Problems

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^Nc_ix_i, subject to ∑_i=1^Nl_ix_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^Nb_i in time. The branch-search algorithm's space requirement is linear in N. Computational experience with these algorithms is presented.