Merging and Sorting Applied to the Zero-One Knapsack Problem

Branch-and-bound algorithms are adequate for the solution of a wide range of 0-1 knapsack problems. It is shown that the simplest method of branching is as good as any. However, problems with highly correlated large weights and values quickly become unsolvable in a reasonable time. This paper develops algorithms that are aimed specifically at the hardest possible examples. The new methods use merging and sorting ideas and require a moderate amount of additional memory space. They are, however, faster by factors far in excess of 1,000 in many cases, thereby extending considerably the range of practically solvable 0-1 knapsack problems.