Efficient linear systolic array for the knapsack problem

A processor-efficient systolic algorithm for the dynamic programming approach to the knapsack problem is presented in this paper. The algorithm is implemented on a linear systolic array where the number of cells q, the cell memory storage a and the input/output requirements are design parameters. These are independent of the problem size given by the number of the objects m and the knapsack capacity c. The time complexity of the algorithm is Q(mc/q+m) and both the time speedup and the processor efficiency are asymptotically optimal. A new procedure for the backtracking phase of the algorithm with a time complexity Q(m) is also proposed. It is an improvement on the usual strategies used for back-tracking which have a time complexity Q(m+c)