Abstract: Based on the two-list algorithm and the two-list four-table algorithm, this paper proposes parallel adaptive algorithm for solving the knapsack problem. It uses processors, time, and memory to solve the knapsack problem , whose parameter can be selected by numbers of processors and amounts of memory that can make full use of the existing hardware resources to find the fastest solution. Experimental results show that the algorithm is effective.

Key words: knapsack problem, NP problem, parallel algorithm, time-memory-processor tradeoff

摘要： 针对二表算法和动态二表算法求解背包问题，提出一个并行自适应算法，能用 个处理机、 的时间、 的空间求解背包问题 ，根据处理机的数目以及存储器的容量来选择参数，充分利用已有的硬件资源，以求得最快的求解速度。实验结果证明了该算法的有效性。

关键词: 背包问题, NP问题, 并行算法, 时间-存储器-处理机折中

CLC Number: 

• TP301.6