背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题,在信息密码学和数论等研究中具有极重要的应用.将求解背包问题著名的二表算法的设计思想应用于三表搜索中,利用分治策略和无存储冲突的最优归并算法,提出一种基于EREW-SI MD共享存储模型的并行三表算法.算法使用O(2n/4)个处理机单元和O(23n/8)的共享存储空间,在O(23n/8)时间内求解n维背包问题.将提出的算法与已有文献结论进行的对比分析表明:文中算法明显改进了现有文献的研究结果,是一种可在小于O(2n/2)的硬件资源上,以小于O(2n/2)的计算时间求解背包问题的无存储冲突并行算法.