scientific article; zbMATH DE number 150456
Let (KP) denote the classical (integral) knapsack problem maximize \(\sum^ m_{j=1} p_ j z_ j\) subject to \(\sum^ m_{j=1} w_ j z_ j\leq c\), \(z_ j\geq 0\) and integer, \(j=1,\dots,m\), for given \(p_ j\), \(z_ j\), \(j=1,\dots,m\), and given \(c\). The aim of this paper is to show how the solution of (KP) by dynamic programming can be implemented on a systolic array. First, a non-modular solution is presented under the assumption that the cells' memory size \(\alpha\) may depend upon the problem size \((\alpha\geq c)\). The time for finding the optimal value of (KP) will be \(2m+c\). In a second, modular, case each celle has an adressable memory of size \(\alpha\), which is independent of the problem size. \(\lceil mc/\alpha\) cells are required to store the problem's data and \(c+\lceil mc/\alpha+m\) time units are necessary for finding (KP)'s optimal value. Repeated use of any cell is possible under the following assumptions: (i) the array consists of unidirectional connected cells each of them with adressable memory of size \(\alpha\); (ii) a memory module receives data from the last cell and sends them to the first; (iii) any cell saves a copy of its results in a common parallel matrix memory connected to one supplementary cell. Features such as the time to obtain (KP)'s optimal value and the queue size requirements are discussed at the end.
- Dynamic programming on two-dimensional systolic arrays
- Parallel Algorithms for Knapsack Type Problems
- scientific article; zbMATH DE number 714583 (Why is no real title available?)
- THE DERIVATION OF UNIFORM RECURRENCE EQUATIONS FOR THE KNAPSACK PROBLEM
- ON THE EXPECTED EXECUTION TIME FOR A CLASS OF NON UNIFORM RECURRENCE EQUATIONS MAPPED ONTO 1D REGULAR ARRAYS
- A systolic algorithm for solving knapsack problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4031601)
