%0 Journal Article
%T An Optimal Parallel Algorithm for the Knapsack Problem<br>背包问题的最优并行算法
%A LI Qing-Hu
%A LI Ken-Li
%A JIANG Sheng-Yi
%A ZHANG Wei
%A <br>李庆华
%A 李肯立
%A 蒋盛益
%A 张薇
%J 软件学报
%D 2003
%I 
%X A new parallel algorithm for the knapsack problem is proposed, in which the method of divide and conquer is adopted. Based on an CREW-SIMD machine with shared memory, the proposed algorithm needs O(2n/4)1-e processors, 0e1, and O(2n/2) memory to find a solution for the n-element knapsack problem in O(2n/4 (2n/4)e) time. The cost of the algorithm is O(2n/2), which is optimal and an improved result over the past researches. The wrong results in corresponding literatures are also pointed out in this paper.
%K knapsack problem
%K NP-complete
%K parallel algorithm
%K method of divide and conquer<br>背包问题
%K NP完全
%K 并行算法
%K 分治法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=E57CCF48E1B1E584&yid=D43C4A19B2EE3C0A&vid=F3583C8E78166B9E&iid=94C357A881DFC066&sid=412FA1328E0CB9E9&eid=B65E5C7BA0DC04DC&journal_id=1000-9825&journal_name=软件学报&referenced_num=12&reference_num=10