40 Years of Computing at Newcastle

Department Technical Report Series No. 389

The Derivation of Uniform Recurrence Equations for the Knapsack Problem

G.M. Megson

University of Newcastle upon Tyne. 1992

Abstract

We propose a mapping procedure for synthesizing uniform recurrence equations from the dynamic programming formulation of the Knapsack problem. The procedure removes the non-regularity in the dependence graph for the problem and allows existing synthesis techniques to be used in the derivation of arrays.