一种求解背包问题的自适应算法  

Adaptive Algorithm for Solving Knapsack Problem

作　　者：江华[1] 谭新星[2] 李祥[1] 

机构地区：[1]贵州大学计算机理论与软件研究所,贵阳550025 [2]广东韶关学院计算机系,韶关512005

出　　处：《计算机工程》2008年第4期7-9,共3页Computer Engineering

基　　金：贵州省科学基金资助项目(GGY2004002)

摘　　要：针对二表算法和动态二表算法求解背包问题,提出一个并行自适应算法,能用2δ个处理机、O(ε2(n-δ)/2)的时间、O(2(n+δ)/2-ε)的空间求解背包问题(0≤δ≤n/5,1≤ε≤(n-δ)/4),根据处理机的数目以及存储器的容量来选择参数,充分利用已有的硬件资源,以求得最快的求解速度。实验结果证明了该算法的有效性。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 26 processors, O（ε2（^n-δ）/2） time, and O（2（^n＋δ）2-ε） memory to solve the knapsack problem （0〈δ≤〈n/5, 1≤ε≤（n-δ）/4）, 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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]