西南交通大学学报(英文版)2003，Vol.11Issue(2)：131-137,7.
An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW
An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW
摘要
Abstract
A new parallel algorithm is proposed for the knapsack problem where the method of divide and conquer is adopted. Based on an EREW-SIMD machine with shared memory, the proposed algorithm utilizes O(2n/4)1-ε processors, 0≤ε≤1, and O(2n/2) memory to find a solution for the n-element knapsack problem in time O(2n/4(2n/4)ε). The cost of the proposed parallel algorithm is O(2n/2), which is an optimal method for solving the knapsack problem without memory conflicts and an improved result over the past researches.关键词
knapsack problem/NP-complete/parallel algorithm/divide and conquerKey words
knapsack problem/NP-complete/parallel algorithm/divide and conquer分类
信息技术与安全科学引用本文复制引用
李肯立,蒋盛益,王卉,李庆华..An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW[J].西南交通大学学报(英文版),2003,11(2):131-137,7.基金项目
Supported by the Natural Science Foundation of China (No.60273075) and the National High Technique Development Program (863-306 ZD-11-01-06). （No.60273075）
