%0 Journal Article
%T 背包问题的最优并行算法
%A 李庆华？
%A 李肯立？
%A 蒋盛益？
%A 张薇？
%J 软件学报
%P 891-896
%D 2003
%X 利用分治策略,提出一种基于simd共享存储计算机模型的并行背包问题求解算法.算法允许使用o(2n/4)1-ε个并行处理机单元,0≤ε≤1,o(2n/2)个存储单元,在o(2n/4(2n/4)ε)时间内求解n维背包问题,算法的成本为o(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.
%K 背包问题
%K np完全
%K 并行算法
%K 分治法
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20030504&flag=1