A SYSTOLIC ALGORITHM FOR SOLVING KNAPSACK-PROBLEMS

doi:10.1080/00207169408804335

標題:	A SYSTOLIC ALGORITHM FOR SOLVING KNAPSACK-PROBLEMS
作者:	LIN, CJ CHEN, SJ 應用數學系 Department of Applied Mathematics
關鍵字:	SYSTOLIC ARRAY;PARALLEL ALGORITHM;TREE;KNAPSACK PROBLEM
公開日期:	1994
摘要:	A systolic algorithm for solving the O/1-knapsack problems with n items is presented. The computational model used is a tree structure which consists of 2(n) identical processing elements (PEs). Each PE executes the same program at any time step. The time complexity varies from n to 3n - 2 steps which includes all the input/output data communication time. The design process and the correctness verification of this algorithm are considered in detail.
URI:	http://hdl.handle.net/11536/2703 http://dx.doi.org/10.1080/00207169408804335
ISSN:	0020-7160
DOI:	10.1080/00207169408804335
期刊:	INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Volume:	54
Issue:	1-2
起始頁:	23
結束頁:	32
Appears in Collections:	Articles